Для начала понадобится отдельная функция или утилита stem(), которая для любого слова вернёт его основу (именно это и делают поисковые движки, в т.ч. Sphinx и Lucene, откуда её и можно достать и использовать в своих целях). Также не помешает функция tokenize(), разбивающая
Если такая функция есть. Проходим по всем словам из словаря (source), а из получившихся основ строим trie, в котором листьями будут соответствующие person_id. Имена из 2 и более слов транслируются в n-граммы соответсвующих основ, разделённые пробелами. Т.е. имя «Иванова Анна Михайловна» будет транслировано во что-то вроде «иванов анн михайловн» (использовать lowercase-фильтр или нет — это уже зависит от приложения и текста: если текст грамотный, то не надо, если «из интернетов», то лучше всё-таки использовать).
Дальше токенизируем текст, стеммим каждое слово и последовательно ищем их в нашем trie. Можно искать сразу триграммы, можно подтягивать второе и третье слово по необходимости (если есть частичное совпадение в trie).
Если trie реализовывать лень, можно заменить их на hash map'ы, но тогда имена из нескольких слов лучше хранить в виде списка, а hash map сделать вложенным (первое слово в hash map'е верхнего уровня указывает на другой hash map, хронящий все возможные вторые слова для указанного первого слова; получается этакое дерево из hash map'ов).
Если считать, что поиск по trie/в hash map'е выполняется за O(1), то весь алгоритм отработает за O(n), где n — количество слов в тексте. При этом не придётся индексировать весь текст, а только структуру для хранения основ имён (индексирование в Lucene/Sphinx, вообще говоря, не самая быстрая операция, а размер индекса около 20-30% от текста, так что не факт, что влезет в память; естественно, я предполагаю, что количество имён меньше размера текста).
Summary:
1. Применить stem() ко всем именам.
2. Сохранить слова в структуру с быстрым поиском (trie/hash map).
3. Токенизировать текст, применить stem() ко всем полученным словам.
4. Пройтись по списку получившихся слов, при этом ища их в структуре с именами.
5. Profit.
Простой
Средний
