Какую структуру данных я должен использовать, чтобы найти похожие строки? - PullRequest
3 голосов
/ 04 июля 2011

Какую структуру данных я должен использовать, чтобы найти похожие строки?Например, когда вы запрашиваете в Google строку «hapyp brithdya», Google спрашивает вас, имеете ли вы в виду «с днем ​​рождения», строку, которая очень похожа на ранее написанную с ошибкой строку «hapyp brithdya».

Какая структура данныхбудет наиболее эффективно выполнять такие операции как в пространстве, так и во времени?

Пожалуйста, помогите.Ваше время очень ценится.

Ответы [ 2 ]

6 голосов
/ 04 июля 2011

Поскольку вы запрашиваете структуру данных, я порекомендую Автоматы Левенштейна .

Они могут быть расширены до вероятностного варианта, который возвращает наиболее вероятный (согласно статистике корпуса).) исправление строки.См. Основную идею эссе "Как написать корректор орфографии" , написанное Google Питером Норвигом;объединение этого с автоматами Левенштейна требует некоторых знаний о конечных преобразователях.См. Хасан, Ноеман и Хасан для более подробной информации.

1 голос
/ 04 июля 2011

Механизм обучения, который использует Google, - это история поиска.Например, я искал «hapyp brithdya», а затем понял, что написание было неправильным и поэтому не выбрал какую-либо ссылку.Мой следующий поиск будет «с днем ​​рождения» правильное написание.И из этой последовательности поисков Google может выяснить, что «hapyp brithdya» на самом деле означало «с днем ​​рождения».

Еще один механизм оценки, основанный на тех же строках, который помогает Google дать более приемлемые исправления орфографии, заключается в том, что поискза "hapyp brithdya", приводящий к клику пользователя по ссылке (предложенной поиском Google), содержащей "happy birthday".Это увеличивает близость слова «с днем ​​рождения» к «хапу бритдья» по сравнению с (скажем) «днем рождения подгузника», который присутствовал в ссылке, которую пользователь не посещал

...