История одного анаграммера.
Mar. 10th, 2013 01:45 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
tebs_sОпишу-ка я историю создания и развития одного анаграммера. Целью этого жизнеописания является желание поделиться опытом и получить отзывы о слабых местах алгоритмов.
Анаграммер, о котором пойдет речь, изначально являлся частью большой программы в помощь штабу для игр в квест. Появился анаграммер до версии 0.3.2.40 от 27.07.2009 (ранее не велась статистика). Значит на данный момент ему почти 4 года. За это время скорость поиска анаграмм по словарю увеличилась относительно первых вариантов в тысячи раз.
Далее появилось желание искать не только строгое соответствие, но еще в двух вариантах. 1) Словарное слово как минимум должно содержать все входные буквы, но не ограничиваться ими. 2) Словарное слово можно собрать из входных букв, используя не все, но не более чем есть, каждую максимум столько раз сколько она встречается. Алгоритм строгого поиска не изменился. Оба эти поиска были одинаковы по принципу алгоритма поиска, разве что менялись местами слова и входная последовательность. Поиск был также перебором, где проверялось что все буквы меньшей последовательности принадлежали также и большей.
Затем внедрено было ограничение по длине искомых слов. Т.о. при переборе по словарю сначала проверялась длина слова, затем уже происходил перебор по буквам. Т.е. при строгом поиске проверялось точное совпадение, при поиске "слов в буквах" длина слова из словаря должна быть не больше кол-ва входных букв, и при поиске "букв в словах" длина должна быть не меньше кол-ва букв. Тогда же и пользователям стало доступно ограничение по длине искомых слова, что при активном использовании значительно уменьшало время поиска.
В версии 0.3.2.55 от 25.09.2009 поиск анаграмм был выведен в отдельный поток. Это позволило работать дальше с программой, пока идет поиск, а также удобно прерывать поиск.
Версия номер WEB
Учитывая ориентированность на использование сайта с мобильных устройств, для исключения переключателя словарей из интерфейса, словари всех языков были слиты в одну таблицу. Затем удалены повторяющиеся слова. Осталось почти 430 тысяч слов. Тупой поиск по словам здесь уже не имел права на существование. Был придуман новый хеш. Общий алфавит из русского, украинского и английского языков состоит из 63 разных букв. Хеш представлял из себя 63 позиции, каждая позиция соответствовала одной букве общего алфавита. На позиции находится цифра, равная кол-ву повторений буквы в слове. Т.е. хеш слова мама выглядит так 200...020...00. На месте многоточий на самом деле многонули :) Строгий поиск анаграмм выполнялся строгим сравнением хеша искомых букв. Не строгий поиск выполняется при помощи регулярных выражений. При поиске слова, содержащего буквы ААБ запрос принимал вид ... WHERE Word_Hash REGEXP '([2-9])([1-9])([0-9]{61})'. При поиск слов в тех же буквах запрос выглядит так: WHERE Word_Hash REGEXP '([0-2])([0-1])([0]{61})'.Индексы БД, конечно, ускоряют поиск, но поиск все равно "не достаточно быстр". Хеш, хоть и состоит из цифр, по сути своей является текстовым, и именно так мы его использовали изначально при анаграммировании. Занимает 63 позиции. Тип поля VARCHAR(63). Если переводить в число, то это 8 байт на хеш (Double). Однако проведя всяческие математические расчеты пришел к выводу, что перевод этого хеша в число интересен только для строго сравнения (ускорение на MySQL от 100 до 500 раз). При нестрогих поисках этот хеш бессмыслен. Например слово состоящее из одной буквы А имеет больший хеш, чем слово длиной много букв, но не содержащего в себе ни одной буквы А. Как вариант были мысли использовать несколько хешей для поиска.
После очередных расчетов, решено было попробовать хеш на основе хеша для настольной программы, но модифицированным (более уникальным). Бралась не просто позиция буквы в алфавите, а число 10 возводилось в степень равную позиции буквы в алфавите. Алфавит оставался отсортированным по частоте. Этим приемом избегалось влияние кол-ва повторений букв в слове на соседние букувы в хеше. Это изменение было проверено на настольной программе. Скорость строго поиска увеличилась приблизительно на 10%, скорость не строгих поисков упала на 10-15%%. Падение скорости скорее всего связано с тем, что хеш перестал умещаться в тип WORD (2 байта) и пришлось использовать Extended (10 байт, плавающая запятая). В Delphi попытки привести хеш к типу Double или Single (описано ниже) дали тот же самый результат, что и с Extended. Ускорение же строгого поиска связано с большей уникальностью хеша.
Подумав еще, а также собрав статистику по объединенному словарю получили вот что. http://clip2net.com/s/4HVV83 Это статистика слов, в которых есть повторения букв. Как видим более 3-х одинаковых букв в слове встречается крайне редко (менее 2,5%). По сути, в вышеописанном хеше используется 10-ричная система счисления, что предполагает от 0 до 9 одинаковых букв в слове без влияния на старший разряд. Как видно из статистики, достаточно использовать 4-х ричную систему счисления (0-3 повторяющихся букв). 2,5% случаев влияния на соседний разряд не внесут существенных проблем при поиске, однако позволят использовать 4-х байтную переменную (Decimal или Single) вместо 10-ти байтной. Что в случае Delphi, на практике, не дает никакого выигрыша в скорости, а даже проигрыш, на 2-5%%.
В WEB версии программы использование как простого хеша из настольной программы (сумма позиций в алфавите), так и хитрого хеша "4-й степени" (по обычному алфавиту) на SQL только замедляет любой поиск. Использование частотно-отсортированного алфавита при поиске "в словах" ускоряет нестрогий поиск до 18% при использовании "простого" хеша и до 15% при использовании хеша "4-й степени". При поиске "в буквах" падение производительности при хеше 4-й степени до 300%. При чем использование этих хешей не отменяет проверку по 63-х позиционному текстовому.
Получается, что хеш 63-х позиционный текстовый самый быстрый в поиске "слов в буквах", числовой 63-х позиционный самый быстрый в строгом поике, и использование 63-х позиционного текстового + хеш "4-й степени" наиболее быстрая связка при поиске "букв в словах".
Посмотрев на объем базы и на ограничение хостера я решил вот что. Оставляем 63-позиционную текстовую маску для нестрогого поиска при помощи regexpr, а также эту же маску, но в виде числа для строго поиска. Использование же хеша "4-й степени" лишь для одного типа поиска с незначительным ускорением не считаю разумным.
На сегодня все вот так и работает. Если есть замечания или предложения по ускорению работы алгоритмов - рад выслушать. Если текст показался запутанным и не ясным - прошу прощения, я старался как мог.
Анаграммер, о котором пойдет речь, изначально являлся частью большой программы в помощь штабу для игр в квест. Появился анаграммер до версии 0.3.2.40 от 27.07.2009 (ранее не велась статистика). Значит на данный момент ему почти 4 года. За это время скорость поиска анаграмм по словарю увеличилась относительно первых вариантов в тысячи раз.
Версия номер раз.
Первичный вариант был довольно прост. Обычный перебор слов по словарю. Перебором же входных букв из по словарному слову проверялось совпадение. Поиск был только строгий, т.е. искались слова с полным совпадением по буквам и их кол-ву с входной последовательностью. Словарь - текстовый файл, одна строка - одно слово. Работало все довольно медленно. Все первые улучшения касались только мелких моментов этого алгоритма. Например выходы из цикла перебора букв по слову при первом же несовпадении, методов вывода результатов на экран и т.п.Далее появилось желание искать не только строгое соответствие, но еще в двух вариантах. 1) Словарное слово как минимум должно содержать все входные буквы, но не ограничиваться ими. 2) Словарное слово можно собрать из входных букв, используя не все, но не более чем есть, каждую максимум столько раз сколько она встречается. Алгоритм строгого поиска не изменился. Оба эти поиска были одинаковы по принципу алгоритма поиска, разве что менялись местами слова и входная последовательность. Поиск был также перебором, где проверялось что все буквы меньшей последовательности принадлежали также и большей.
Затем внедрено было ограничение по длине искомых слов. Т.о. при переборе по словарю сначала проверялась длина слова, затем уже происходил перебор по буквам. Т.е. при строгом поиске проверялось точное совпадение, при поиске "слов в буквах" длина слова из словаря должна быть не больше кол-ва входных букв, и при поиске "букв в словах" длина должна быть не меньше кол-ва букв. Тогда же и пользователям стало доступно ограничение по длине искомых слова, что при активном использовании значительно уменьшало время поиска.
В версии 0.3.2.55 от 25.09.2009 поиск анаграмм был выведен в отдельный поток. Это позволило работать дальше с программой, пока идет поиск, а также удобно прерывать поиск.
На этом, можно сказать, первая версия алгоритма закончила развитие. Удобством этого алгоритма была возможность на лету подкладывать словари без специальной предварительной подготовки. Минусы - скорость работы. Все возможные оптимизации алгоритма и кода, оптимизация использования памяти и процессорного времени привели лишь к ускорению работы анаграммера не более чем на 20%.
Версия номер два.
В версии 0.3.4.87 от 26.11.2010 были внедрены индексы слов в словарях. Индекс состоял из 2-х значений для каждого слова: длина и некий хеш. Хешом являлась сумма позиций букв слова в алфавите. Например у слова мама индекс был 4,30, где 4 - это длина слова, а 30=14(м)+1(а)+14(м)+1(а). Соответственно вычислялся такой же индекс и для входной последовательности. Дальше поиск выполнялся перебором по индексу. Сначала проверялась длина, затем хеш. При строгом поиске хеш слова должен был совпадать с хешем входных букв, при не строгом быть или больше или меньше, в зависимости от типа поиска. Если выполнялись оба условия, по длине и хешу, тогда выполнялась уже обычная проверка перебором по слову.
Ускорение поиска было двукратным. Однако теперь подкладывать словари на лету стало не возможно - нужно было построить индекс. Учитывая, что за 1,5 года существования этой возможности никто ей не воспользовался, то потерей можно пренебречь.
К версии 0.3.6.130 от 03.05.2012 я себя таки пересилил и разбил словарь на субсловари по длине слов. Т.е. словарь теперь состоял не из одного файла, а из пары десятков. Длина из индекса была выброшена за ненадобностью. Теперь при поиске осуществлялся перебор только по тем субсловарям, длина слов в которых удовлетворяла условиям поиска. Ускорение поиска было до 120 раз, в зависимости от условий поиска.
К следующей версии (0.3.6.131 от 16.05.2012) я вывел поиск по каждому из субсловарей в отдельный поток. При поиске слов с разными длинами поиск выполнялся, условно, столько же, сколько поиск по самому длинному субсловарю. К сожалению у меня не осталось записей об изменении скорости поиска, да и зависимость там была явно не линейная.
В эпохальной версии 0.3.6.136 от 19.07.2012 изменений было множество. Для начала введен был кеш поиска. Т.е. каждый результат поиска сохранялся на диске, и при следующем таком же поиске результат просто считывался из кеша. Также не мало изменений коснулось и методов вывода результатов, их представления и сортировки. Но речь не об этом. Хеш слов в словаре был немного изменен. Хеш по прежнему был суммой позиций букв, однако не в простом алфавите, а отсортированном по частоте появления букв в словах. Использовалась статистика из интернетов. Т.о. русский алфавит стал выглядеть так: ёфэщцюшжхйчгъьбызяупдмклврстниаео. Но использовал я его в перевернутом задом-наперед варианте. Получалось что самая редкая буква имеет самую большую позицию, а значит чем больше хеш при одинаковой длине, тем больше шансов что там редкая буква. Частые буквы же не вносят большой лепты в разницу между хешами. Этот прием ускорил поиск за счет большей уникальности хеша в несколько раз.
На этом развитие алгоритма поиска анаграмм настольной программы приостановилось на долго.
К версии 0.3.6.130 от 03.05.2012 я себя таки пересилил и разбил словарь на субсловари по длине слов. Т.е. словарь теперь состоял не из одного файла, а из пары десятков. Длина из индекса была выброшена за ненадобностью. Теперь при поиске осуществлялся перебор только по тем субсловарям, длина слов в которых удовлетворяла условиям поиска. Ускорение поиска было до 120 раз, в зависимости от условий поиска.
К следующей версии (0.3.6.131 от 16.05.2012) я вывел поиск по каждому из субсловарей в отдельный поток. При поиске слов с разными длинами поиск выполнялся, условно, столько же, сколько поиск по самому длинному субсловарю. К сожалению у меня не осталось записей об изменении скорости поиска, да и зависимость там была явно не линейная.
В эпохальной версии 0.3.6.136 от 19.07.2012 изменений было множество. Для начала введен был кеш поиска. Т.е. каждый результат поиска сохранялся на диске, и при следующем таком же поиске результат просто считывался из кеша. Также не мало изменений коснулось и методов вывода результатов, их представления и сортировки. Но речь не об этом. Хеш слов в словаре был немного изменен. Хеш по прежнему был суммой позиций букв, однако не в простом алфавите, а отсортированном по частоте появления букв в словах. Использовалась статистика из интернетов. Т.о. русский алфавит стал выглядеть так: ёфэщцюшжхйчгъьбызяупдмклврстниаео. Но использовал я его в перевернутом задом-наперед варианте. Получалось что самая редкая буква имеет самую большую позицию, а значит чем больше хеш при одинаковой длине, тем больше шансов что там редкая буква. Частые буквы же не вносят большой лепты в разницу между хешами. Этот прием ускорил поиск за счет большей уникальности хеша в несколько раз.
На этом развитие алгоритма поиска анаграмм настольной программы приостановилось на долго.
Версия номер WEB
И тут наступило правильное время, появилось немного свободного времени, а также желание осваивать новые горизонты и выполнить таки пожелания команды в мобильности нашей программы. Я начала переносить функционал программы на вебку. PHP+MySQL+JqueryMobile. Все для меня новое. Когда пришло время анаграммайзера, было принято решение о доработке алгоритма.
Учитывая ориентированность на использование сайта с мобильных устройств, для исключения переключателя словарей из интерфейса, словари всех языков были слиты в одну таблицу. Затем удалены повторяющиеся слова. Осталось почти 430 тысяч слов. Тупой поиск по словам здесь уже не имел права на существование. Был придуман новый хеш. Общий алфавит из русского, украинского и английского языков состоит из 63 разных букв. Хеш представлял из себя 63 позиции, каждая позиция соответствовала одной букве общего алфавита. На позиции находится цифра, равная кол-ву повторений буквы в слове. Т.е. хеш слова мама выглядит так 200...020...00. На месте многоточий на самом деле многонули :) Строгий поиск анаграмм выполнялся строгим сравнением хеша искомых букв. Не строгий поиск выполняется при помощи регулярных выражений. При поиске слова, содержащего буквы ААБ запрос принимал вид ... WHERE Word_Hash REGEXP '([2-9])([1-9])([0-9]{61})'. При поиск слов в тех же буквах запрос выглядит так: WHERE Word_Hash REGEXP '([0-2])([0-1])([0]{61})'.Индексы БД, конечно, ускоряют поиск, но поиск все равно "не достаточно быстр". Хеш, хоть и состоит из цифр, по сути своей является текстовым, и именно так мы его использовали изначально при анаграммировании. Занимает 63 позиции. Тип поля VARCHAR(63). Если переводить в число, то это 8 байт на хеш (Double). Однако проведя всяческие математические расчеты пришел к выводу, что перевод этого хеша в число интересен только для строго сравнения (ускорение на MySQL от 100 до 500 раз). При нестрогих поисках этот хеш бессмыслен. Например слово состоящее из одной буквы А имеет больший хеш, чем слово длиной много букв, но не содержащего в себе ни одной буквы А. Как вариант были мысли использовать несколько хешей для поиска.
После очередных расчетов, решено было попробовать хеш на основе хеша для настольной программы, но модифицированным (более уникальным). Бралась не просто позиция буквы в алфавите, а число 10 возводилось в степень равную позиции буквы в алфавите. Алфавит оставался отсортированным по частоте. Этим приемом избегалось влияние кол-ва повторений букв в слове на соседние букувы в хеше. Это изменение было проверено на настольной программе. Скорость строго поиска увеличилась приблизительно на 10%, скорость не строгих поисков упала на 10-15%%. Падение скорости скорее всего связано с тем, что хеш перестал умещаться в тип WORD (2 байта) и пришлось использовать Extended (10 байт, плавающая запятая). В Delphi попытки привести хеш к типу Double или Single (описано ниже) дали тот же самый результат, что и с Extended. Ускорение же строгого поиска связано с большей уникальностью хеша.
Подумав еще, а также собрав статистику по объединенному словарю получили вот что. http://clip2net.com/s/4HVV83 Это статистика слов, в которых есть повторения букв. Как видим более 3-х одинаковых букв в слове встречается крайне редко (менее 2,5%). По сути, в вышеописанном хеше используется 10-ричная система счисления, что предполагает от 0 до 9 одинаковых букв в слове без влияния на старший разряд. Как видно из статистики, достаточно использовать 4-х ричную систему счисления (0-3 повторяющихся букв). 2,5% случаев влияния на соседний разряд не внесут существенных проблем при поиске, однако позволят использовать 4-х байтную переменную (Decimal или Single) вместо 10-ти байтной. Что в случае Delphi, на практике, не дает никакого выигрыша в скорости, а даже проигрыш, на 2-5%%.
В WEB версии программы использование как простого хеша из настольной программы (сумма позиций в алфавите), так и хитрого хеша "4-й степени" (по обычному алфавиту) на SQL только замедляет любой поиск. Использование частотно-отсортированного алфавита при поиске "в словах" ускоряет нестрогий поиск до 18% при использовании "простого" хеша и до 15% при использовании хеша "4-й степени". При поиске "в буквах" падение производительности при хеше 4-й степени до 300%. При чем использование этих хешей не отменяет проверку по 63-х позиционному текстовому.
Получается, что хеш 63-х позиционный текстовый самый быстрый в поиске "слов в буквах", числовой 63-х позиционный самый быстрый в строгом поике, и использование 63-х позиционного текстового + хеш "4-й степени" наиболее быстрая связка при поиске "букв в словах".
Посмотрев на объем базы и на ограничение хостера я решил вот что. Оставляем 63-позиционную текстовую маску для нестрогого поиска при помощи regexpr, а также эту же маску, но в виде числа для строго поиска. Использование же хеша "4-й степени" лишь для одного типа поиска с незначительным ускорением не считаю разумным.
На сегодня все вот так и работает. Если есть замечания или предложения по ускорению работы алгоритмов - рад выслушать. Если текст показался запутанным и не ясным - прошу прощения, я старался как мог.
