MihanEntalpo blog Php, javascript, jquery, yii, webasyst, nginx, Python и все-все-все

Бывает, что нужно найти в списке слов наиболее похожие на заданное слово.
Например, если у вас есть список городов, и нужно найти среди них наиболее похожий на то, что ввёл пользователь, даже если при вводе пользователь допустил ошибки.

При этом, разумеется, есть мощные профессиональные системы поиска, такие как Sphinx, ElasticSearch, но не всегда имеет смысл их разворачивать и настраивать, ради одной небольшой задачи, либо когда вам только нужно сделать прототип поиска, чтобы проверить, даст ли он требуемые преимущества.

Для таких случаев я написал на php инструмент для нечеткого поиска среди массива строк.

В каких случаях может пригодится данный инструмент:

1. Поиск среди списка стран мира

2. Поиск среди названий страниц вашего сайта в админ-панели

3. Поиск среди уникальных имён ваших пользователей

и в других случаях, где количество записей списка не превышает несколько тысяч.

Я, например, написал этот инструмент для того, чтобы разделять поле ФИО, в которое люди вписывают имя, фамилию и отчество в произвольном формате, на отдельные поля Имя, Фамилия и Отчество, с соответствующими значениями.

Где взять:

Можно взять класс FastFuzzySearch прямо из репозитория:
https://github.com/MihanEntalpo/FastFuzzySearch

Также, можно установить FastFuzzySearch с использованием composer:

В вашем файле composer.json нужно прописать:

{
    "require": {
        "mihanentalpo/fast-fuzzy-search": "*"
    }
}

Установить:

composer.phar install

Использование:

<?php
//Подключаем файл
require_once("FastFuzzySearch.php");
//Формируем список слов, среди которых будем искать (мужские русские имена на букву "А"):
$words = array(
    "Абакум", "Абрам", "Абросим", "Аввакум", "Август", "Авдей", "Авдий", 
    "Авель", "Авенир", "Аверий", "Аверкий", "Аверьян", "Авксентий", "Авраам", 
    "Авраамий", "Аврам", "Аврамий", "Аврелиан", "Автоном", "Агап", "Агапий", 
    "Агапит", "Агафангел", "Агафон", "Аггей", "Адам", "Адриан", "Азар", 
    "Азарий", "Акакий", "Акила", "Аким", "Акиндин", "Акинф", "Акинфий", 
    "Аксён", "Аксентий", "Александр", "Алексей", "Алексий", "Альберт", 
    "Альфред", "Амвросий", "Амос", "Амфилохий", "Ананий", "Анастасий", 
    "Анатолий", "Андрей", "Андриан", "Андрон", "Андроний", "Андроник", 
    "Анект", "Анемподист", "Аникей", "Аникий", "Аникита", "Анисий", 
    "Анисим", "Антиох", "Антип", "Антипа", "Антипий", "Антон", "Антонин", 
    "Антроп", "Антропий", "Ануфрий", "Аполлинарий", "Аполлон", "Аполлос", 
    "Ардалион", "Ареф", "Арефий", "Арий", "Аристарх", "Аристид", "Аркадий", 
    "Арнольд", "Арон", "Арсен", "Арсений", "Арсентий", "Артамон", "Артём", 
    "Артемий", "Артур", "Архип", "Асаф", "Асафий", "Аскольд", "Афанасий", 
    "Афиноген", "Афинодор", "Африкан"
);
//Создаём объект для быстрого поиска:
$ffs = new FastFuzzySearch($words);
 
//Вот что ввёл пользователь (да, с ошибкой):
$input = "аниисий";
 
//Находим 5 наиболее похожих результатов:
$results = $ffs->find($input, 5);
 
//Выводим результат:
echo "Наиболее похожие на введённое слово '$input':\n";
foreach($results as $res)
{
    echo $res['word'] . ", процент сходства: " . round($res['percent']*100, 2) . "%\n";
}

Программа выведет:

Наиболее похожие на введённое слово 'аниисий':
анисий, процент сходства: 66.67%
аникий, процент сходства: 25%
алексий, процент сходства: 20%
анастасий, процент сходства: 19.05%
аникей, процент сходства: 16.67%

Принцип действия

Работа программы основана на алгоритме, основанном на так называемых n-gram’ах, похожем на алгоритм шинглов.

Для понимания её работы можно взглянуть на вот такую простую функцию для нечёткого сравнения двух строк (приведена для примера, в FastFuzzySearch она не используется):

/**
 * Нечеткое сравнение строк
 * @param первая строка $str1
 * @param вторая строка $str2
 * @param минимальный кусочек интервала сравнения $minSize
 * @param максимальный кусочек интервала сравнения $maxSize - если равен 0, то будет задан автоматически
 * @param string $encoding кодировка текста (обычно - utf-8)
 * @return float число от 0 до 1 - процент совпадения.
 */
function fuzzyCompare($str1,$str2,$minSize=2,$maxSize=4,$encoding='utf-8', $minPercent=1)
{
    $s1 = mb_strlen($str1,$encoding);
    $s2 = mb_strlen($str2,$encoding);
    if ($maxSize==0) $maxSize = min($s1,$s2);
    $maxSize = min($maxSize,$s1,$s2);
    $cnt = 0;
    $num = 0;
    if ($s1>$s2)
    {
        $from = $str1;
        $where = $str2;
        $S = $s1;
    }
    else
    {
        $from = $str2;
        $where = $str1;
        $S = $s2;
    }
 
    for($size = $minSize; $size<$maxSize; $size++)
    {
        for ($i=0;$i<$S - $size+1; $i++)
        {
            $cnt+=1;
            $part = mb_substr( $from,$i,$size,$encoding);
            if ( mb_strpos($where,$part,0,$encoding)!==FALSE )
            {
                    $num+=1;
            }
        }
    }
 
    if ($cnt==0) return 0;
    return $num/$cnt;
}

принцип её действия таков:
1) Разбиваем одну строку (более длинную) на кусочки переменной длины, например, из 2, 3, 4 последовательных символов, считаем количество этих кусочков. Например, слово «алгоритм», при разбитии на кусочки от 2-х до 4-х байт даст нам: «ал», «лг», «го», «ор», «ри», «ит», «тм», «алг», «лго», «гор», «ори», «рит», «итм», «алго», «лгор», «гори», «орит», «ритм» (итого 18 штук)
2) Считаем, какие из кусочков есть во второй строке. Например, в слове «алкоголь», из представленных выше кусочков есть «ал» и «го» (2 штуки)
3) Делим количество кусочков, которые есть во второй строке, на общее их количество, и получаем результирующий «процент сходства». Считаем 2/18 = 0.11111 или 11.1% сходства между словами «алгоритм» и «алкоголь».

Изменяя параметры $minSize, $maxSize можно настраивать качество сравнения (для каждой задачи эти параметры могут быть разными).

Разумеется, можно было бы построить механизм поиска наиболее схожих слов на базе этой функции, и в первой версии так оно и было.

Сейчас же алгоритм FastFuzzyCompare, хотя и аналогичен этой функции, но ориентирован на быстрый поиск похожих слов среди заданного массива, благодаря построенному индексу:
1. При инициализации класса (в конструкторе, или в функции init) строится полный индекс по всем кусочкам всех слов, среди которых надо искать похожие.
2. При вызове функции find анализируемое слово разбивается на кусочки, и среди индекса определяется, какие из них существуют в базе, и для них составляется список слов, содержащих данные кусочки. После этого, проводится суммирование найденных кусочков для каждого слова, и слова сортируются по убыванию отношения найденных кусочков к общему количеству кусочков в данном слове.

Данный подход позволяет добиться высокого быстродействия, в десятки раз превышающего метод последовательного сравнения слов с помощью функции fuzzy_compare, а также с помощью функций levenshtein и similar_text (которые, кстати, дают совсем небольшое ускорение по отношению к fuzzy_compare)

Ускорение инициализации

Поскольку время инициализации (формирования исходного индекса) пропорционально количеству слов, а также, квадрату средней длины слова, при больших наборах слов и длинных словах инициализация может занимать большее время чем хотелось бы. Для решения этой проблемы существует механизм сериализации индекса.
Для этого есть две функции — serializeIndex, для преобразования индекса в строку и unserializeIndex для обратного преобразования из строки во внутреннее состояние. Использование сериализации индекса позволяет многократно увеличить скорость инициализации поиска.
Использование:

//Инициализируем объект как обычно
$ffs = new FastFuzzySearch($words);
//Получаем сериализованный индекс (это строка)
$index = $ffs->serializeIndex();
//Сохраняем его (не обязательно в файле, можно в memcached, redis или даже mysql)
file_put_contents("./index.cache", $index);
....
//В следующий раз создаём объект без указания массива слов:
//при этом объект находится в неинициализированном состоянии, и пользоваться им ещё нельзя.
$ffs = new FastFuzzySearch();
//Прочитаем сериализованный индекс (опять же, из memcached будет быстрее):
$index = file_get_contents("./index.cache");
//Загрузим сериализованный индекс в объект:
$ffs->unserializeIndex($index);

Быстродействие

Для проверки быстродействия был написан скрипт, формирующий массивы слов разного размера, и запускающий поиск среди них тремя способами: с помощью быстрого нечёткого поиска, с помощью расстояния левештейна и с помощью функции similar_text. Такие функции как metaphone и soundex я не стал использовать, так как назначение у них другое — находить похожие по звучанию слова. В моём же случае, поиск найдёт даже не слишком похожие по звучанию, но, при этом, близкие по нечёткому сравнению.

Как раз для этой цели в класс FastFuzzySearch добавлены функции findByLevestaine и findBySimilarText.
Сам код проверки на быстродействие находится в файле /examples/example2.php из упомянутого выше репозитория.

При проверке производится поиск 200 слов по массиву, состоящему из 21376 слов (это список всех более-менее крупных городов России, повторённый 16 раз для увеличения сложности).

Результат:

Testing FastFuzzyCompare...
Testing FindByLevenstaine...
Testing FindBySimilarText...
Поиск 200 среди 21376 слов
Результаты:
Инициализация с нуля: 3.4702 сек.
Сериализация индекса: 0.03133 сек.
Инициализация из сериализованного индекса: 0.10813 сек.
FastFuzzySearch: 0.50727 сек.
Levensteine:     21.96609 сек. (медленнее чем find в 43.3 раз)
SimilarText:     20.13451 сек. (медленнее чем find в 39.69 раз)

Здесь:
Инициализация с нуля — это построение поискового индекса FastFuzzySearch по переданному массиву.
Сериализация индекса — это преобразование поискового индекса в строку для хранения её в кэше, и быстрой загрузки (если ваш массив, по которому требуется искать, не меняется каждый раз — имеет смысл вместо перестроения индекса просто закешировать его где-то (в memcache, в файле, в базе данных), чтобы быстро загружать перед использованием)
Инициализация из сериализованного индекса — это как раз процесс загрузки сериализованного индекса, вместо построения с нуля. Как видно, этот процесс в 30 раз быстрее чем инициализация с нуля, причём, чем больше слов в индексе, тем больше этот разрыв.

Как несложно заметить, функция FastFuzzySearch->find работает достаточно быстро, чтобы использовать её в случаях, когда требуется, например, подсказывать пользователю исправленный вариант введённого им с ошибками запроса, когда вариантов не слишком много.

Зависимость быстродействия от входных данных

С помощью скрипта из файла example3.php можно проверить, как меняется быстродействие алгоритма в зависимости от количества данных, и их свойств.

Выводы сделанные в ходе экспериментов:

1) При росте количества строк в индексе довольно быстро растёт объём индекса (в байтах), и время его построения, однако скорость поиска снижается весьма медленно.

2) При росте длины строк в индексе, вплоть до 640 байт, размер индекса растёт очень быстро, вплоть до 300МБ, полученных в эксперименте, скорость же поиска практически никак не меняется.

3) При увеличении длины искомого слова, время поиска увеличивается пропорционально квадрату длины слова.