Кто-то минусанул все мои комменты в этой ветке, а мне ведь удалось ужать все 20 битные хеши без урезаний + прочие данные в 61КБ.
И порядка 3400 байт занимает код.
Меня тоже удивляют цифры с результатами выше 80%.
Добился пока что 73% на тесткейсе из 100 тысяч слов, есть ещё пара мыслей, попробую, может ещё получится 0.5-1% выжать из решения.
Ну пока что мне удалось уместить это в 72КБ.
Вообще, можно и нужно функцию хеширования переделать. А потом уже можно будет эксперементировать с обрезанием части хешей, чтобы запихнуть всё содержимое вместе с исходниками в 64КБ.
У crc32 слишком много хешей от не слов пересекаются с хешами от слов.
Ещё были мысли, в хеш зашивать доп-информацию о слове, например, биты отвечающие за чётность/нечётность числа обозначающего длину слова, и т.п.
Но у меня получается, что на 1 хеш приходится довольно много срабатываний разных слов, поэтому эту идею пока что забросил.
Уже приблизился к такому результату:
success: 69.5%
negatives: 32.79%
positives: 67.21%
Тут ещё мысль пришла, можно ведь выбрать некое число бит под хеш, полный список всех хешей можно сгенерировать скриптом в отсортированном порядке, затем погонять тесты так, чтобы собралась некоторая статистика true и false срабатываний по каждому хешу. Затем всему этому списку хешей можно в оконцовке поставить бит 0 или 1, в зависимости того как часто срабатывало попадание слова в словарь. Ну и в итоге достаточно будет хранить лишь 1 бит на хеш, т.е. в 64к поместится 512000 бит. Например, мой словарь который получился по metaphone+crc32 уже можно уместить без потерь, даже не применяя gzip сжатия.
Прошу прощения, поторопился опубликовать предыдущий коммент. На самом деле там не такой результат получается, а намного хуже. Во время экспериментов внёс баг в сам счётчик ошибок, после исправления которого на том же тесткейсе получились вот такие цифры:
При таком сжатии получается на 10 тысячах слов из тесткейсов следующее:
success: 81.53%
negatives: 100%
positives: 0%
т.е. наблюдаю то, что функция test отлично справляется с возвращением значения true (ни единой ошибки), а все ошибки связаны возвращением значения false.
И ещё такой момент, список хешей можно отсортировать, а затем привести к одинаковой длинне в битах и эту таблицу вместо длинного столбца развернуть в несколько строк, эти строки лучше жмутся.
Не пробовали анализировать морфологию слов? Чередование гласных с согласными, удобство произношения слов в слух и т.п.?
Я вот попробовал прогнать словарь с помощью функции metaphone (Функция metaphone была написана Lawrence Philips и описана в книге [«Practical Algorithms for Programmers», Binstock & Rex, Addison Wesley, 1995].), получился словарь не порядка 660 тысяч слов, а уже порядка 250 тысяч. При этом % угадываний на тесткейсах колеблется между 75-80%.
Хеши от 660 тыс. слов у меня получилось ужать в 429K (только данные), новый словарь пока не пробовал ужимать.
Да уж, с первой попытки дало 57% на 10000 слов из тесткейсов. Что-то даже страшно стало представить себе, чем там занимаются те, у кого уже за 80% перевалило :)
В жизни то диалоги, думаю, сильно будут отличаться от сериальных.
Может быть стоит выдернуть слова из ютубовских роликов, где люди в компаниях разговаривают в естественной среде, а не на камеру.
Кстати, заодно, можно ещё расклассифицировать по типу обстановки, в которой происходят диалоги.
solution.min.js (1439 B)
data.gz (63761 B, gunzip before use)
Ещё (65535-63761-1439= 335B в запасе осталось).
Надеюсь, всё правильно сделал.
И порядка 3400 байт занимает код.
Добился пока что 73% на тесткейсе из 100 тысяч слов, есть ещё пара мыслей, попробую, может ещё получится 0.5-1% выжать из решения.
Вообще, можно и нужно функцию хеширования переделать. А потом уже можно будет эксперементировать с обрезанием части хешей, чтобы запихнуть всё содержимое вместе с исходниками в 64КБ.
У crc32 слишком много хешей от не слов пересекаются с хешами от слов.
Но у меня получается, что на 1 хеш приходится довольно много срабатываний разных слов, поэтому эту идею пока что забросил.
Уже приблизился к такому результату:
success: 69.5%
negatives: 32.79%
positives: 67.21%
Тут ещё мысль пришла, можно ведь выбрать некое число бит под хеш, полный список всех хешей можно сгенерировать скриптом в отсортированном порядке, затем погонять тесты так, чтобы собралась некоторая статистика true и false срабатываний по каждому хешу. Затем всему этому списку хешей можно в оконцовке поставить бит 0 или 1, в зависимости того как часто срабатывало попадание слова в словарь. Ну и в итоге достаточно будет хранить лишь 1 бит на хеш, т.е. в 64к поместится 512000 бит. Например, мой словарь который получился по metaphone+crc32 уже можно уместить без потерь, даже не применяя gzip сжатия.
success: 68.15%
negatives: 0%
positives: 100%
success: 81.53%
negatives: 100%
positives: 0%
т.е. наблюдаю то, что функция test отлично справляется с возвращением значения true (ни единой ошибки), а все ошибки связаны возвращением значения false.
Я вот попробовал прогнать словарь с помощью функции metaphone (Функция metaphone была написана Lawrence Philips и описана в книге [«Practical Algorithms for Programmers», Binstock & Rex, Addison Wesley, 1995].), получился словарь не порядка 660 тысяч слов, а уже порядка 250 тысяч. При этом % угадываний на тесткейсах колеблется между 75-80%.
Хеши от 660 тыс. слов у меня получилось ужать в 429K (только данные), новый словарь пока не пробовал ужимать.
Может быть стоит выдернуть слова из ютубовских роликов, где люди в компаниях разговаривают в естественной среде, а не на камеру.
Кстати, заодно, можно ещё расклассифицировать по типу обстановки, в которой происходят диалоги.