Поиск и выделение слов в тексте (Алгоритм)

Question

[winbackgo]

Есть база людей, каждая запись может содержать неограниченное кол-во синонимов (имена написанные на разных языках, клички и т.д.). Все записи (как синонимы, так и названия) абсолютно уникальны. По этим данным строиться индекс таблица (назовем ее source) которая может быть представлена так:

name VARCHAR(128),
person_id INT(10),
UNIQUE KEY name (name)

Итак, стоит задача, найти и выделить в тексте слова найденные в базе. Задача усложняется тем, что в тексте имена могут быть в разной падежной форме.

Мой велосипед:

• На базе source строим индекс в sphinx состоящий из триграмм, отбрасываем записи длиною менее 2 символов.
• В тексте выбираем все слова которые начинаются с заглавной буквы, игнорируя двухсимвольные. Если слова идут подряд, то считаем их как одно (ФИО). С опаской относимся к словам в начале предложений.
• Превращаем их в триграммы и кидаем запрос сфинксу.
• Выбираем из результата одно самое подходящее и далее выделяем его в тексте.

Подразумеваю что порог ошибок в данном случае будет около 5%, что в принципе допустимо (ошибочное можно исправить вручную).

В общем, хотел бы узнать: Какие недочеты есть в моем алгоритме и какие могут быть предложения по улучшению? Какие существуют решения похожих задач (наверняка есть, но что-то я туплю, или красивых слов не знаю, поэтому гугл не дает ничего вразумительного)? Как бы вы решили эту задачу?

Comments

[1010101001000100110100111]

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

Как искать?
Берете текст, выдергиваете все слова, приводите их к нужному регистру, и (если нужен нечеткий поиск) для каждого слова удаляете по одной буковке. В итоге, для каждого слова получаете набор слов с выбитыми буквами, для которых считаете хеши. Если один их хешей присутствует в базе — выделяете это слово, иначе — пропускаете.

[winbackgo]

>> Для начала постройте полный список всех словоформ (с учетом падежей и прочее).
Это невозможно, их очень много + добавляются новые в авторежиме.

[1010101001000100110100111]

Так и достраивайте в авторежиме по-аналогии с имеющимися (пробуйте автоматически выявлять парадигму словообразования для новых добавляемых слов)

[winbackgo]

Ваша идея понятна. Спасибо. Но мне кажется использование триграмм будет более эффективным. Вот несколько ссылок по теме habrahabr.ru/post/78566/ habrahabr.ru/post/61807/

Answer 1

[ffriend]

Для начала понадобится отдельная функция или утилита 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.

Comments

[winbackgo]

Спасибо за развернутый ответ. Буду пробовать. Имен на самом деле много, окло 200к, но скорость не так важна, т.к. это будет делаться при публикации или же если это будет мешать быстрой публикации, то в отдельном процессе после публикации.
Планирую использовать сфинкс, надо разобраться как там получить stem.

[grossws]

200к это совсем копеечный объем, оно влезает в память с лихвой. Реализацию стеммера можно глянуть тут: lucene.apache.org/. Чем он плох написал выше.

Answer 2

[grossws]

Умные слова: словоформа, нормализация, компьютерная лингвистика, стеммер Портера, aot, mystem. Для начала, надеюсь хватит.

И кстати, «хватит извращений, откапывайте стюардессу». Посмотрите на apache solr (сделан на lucene).

Comments

[winbackgo]

Извините, а при чем тут морфология, нормализация и т.д.?

[1010101001000100110100111]

А, еще, MySpell/ASpell/PSpell/Hunspell/*Spell

[winbackgo]

Задач стоит в том чтобы сделать тоже самое что sphinx excerpts или lucene highlighter только не подсвечивать заданные ключевые слова в результатах поиска, а наоборот и искать из миллиона слов в индексе совпадения в заданном тексте. Был бы очень рад найти готовое решение и не париться с реализацией.

[grossws]

При создании поискового индекса (что в sphinx, что в solr/elasticsearch/lucene) слова сначала нормализуются, чтобы не раздувать индекс. Т. е. две разных словоформы должны одинаково приводить к хиту. Поэтому то, что предлагает 1010101001000100110100111 выглядит идиотизмом (в смысле, загнать в индекс все словоформы).
Вы все равно хотите подсвечивать хиты из индекса. Оно, конечно, относительно дорого, но реалистично. Далее Вы берете токенизатор и проходите по всему тексту, нормализуя слова и проверяете каждое встретившееся впервые на наличие в индексе. Если индекс влезет в память — будет быстро, если нет — такова судьба.
Стеммер Портера не лучшее решение, хотя и простое. Например, Иванов и Иванова будут иметь разную норму (Иван и Иванов, соответственно).

Answer 3

[winbackgo]

Не совсем мне понятно где в trie место для person_id.

Comments

[winbackgo]

Промахнулся(

[ffriend]

На листьях. Trie — это тот же ассоциативный массив, просто со специфической структурой хранения и поиска.

[winbackgo]

т.е. это будет выглядеть так? (скажем для имени Maya):

{
	"m": {
		"ma": {
			"may": {
				"maya": {
					"_id_": 5
				}
			}
		}
	}
}

[ffriend]

Да, именно так.