Как исправить пользовательский ввод (вид google "вы имели в виду?" )

У меня есть следующее требование: -

У меня много (скажем, 1 миллион) значений (имен). Пользователь будет вводить строку поиска.

Я не ожидаю, что пользователь правильно назовет имена.

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

Мой вопрос: - 1) Я считаю, что хранить эти данные в РСУБД нецелесообразно. Потому что тогда у меня не будет фильтра по SQL-запросам. И мне нужно выполнить полное сканирование таблицы. Итак, в этой ситуации, как данные должны храниться?

2) Второй вопрос такой же, как . Но только для полноты моего вопроса: как я могу выполнить поиск через большой набор данных? Предположим, есть имя Фрэнки в наборе данных. Если пользователь набирает имя Phranky, как мне соответствовать Franky? Нужно ли мне перебирать все имена?

Я наткнулся на Levenshtein Distance, что будет хорошей техникой для поиска возможных строк. Но опять же, мой вопрос заключается в том, что я должен использовать все 1 миллион значений из моего хранилища данных?

3) Я знаю, Google делает это, наблюдая за поведением пользователей. Но я хочу сделать это, не наблюдая за поведением пользователя, т.е. Используя, я еще не знаю, скажу дистанционные алгоритмы. Поскольку для первого метода потребуется большой объем поиска, начинайте с!

4). Как Кирк Бродхерст в , есть два возможных сценария:

Пользователи ошибочно принимают слово (редактировать дистанционный алгоритм)
Пользователи, которые не знают слова и угадывают (алгоритм фонетического соответствия)

Меня интересует обоим. Они действительно две разные вещи; например Шон и Шон звучат одинаково, но имеют расстояние редактирования 3 - слишком высокое, чтобы считаться опечаткой.

Ответ 1

Алгоритм Soundex может помочь вам в этом.

http://en.wikipedia.org/wiki/Soundex

Вы можете предварительно генерировать значения soundex для каждого имени и хранить его в базе данных, а затем индексировать это, чтобы избежать необходимости сканировать таблицу.

Ответ 2

алгоритм битпа предназначен для нахождения приблизительного соответствия в тексте. Возможно, вы могли бы использовать это для вычисления вероятных совпадений. (он основан на Расстояние Левенштейна)

(Обновление: прочитав Ben S ответ (используйте существующее решение, возможно aspell) - это путь)

Как говорят другие, Google делает автоматическую коррекцию, наблюдая, как пользователи исправляют себя. Если я ищу "someting" (sic), а затем сразу для "something", очень вероятно, что первый запрос был неправильным. Возможная эвристика для обнаружения этого:

Если пользователь выполнил два поиска за короткое время и
первый запрос не дал никаких результатов (или пользователь не нажал ни на что)
второй запрос дал полезные результаты
два запроса похожи (имеют небольшое расстояние Левенштейна)

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

Обратите внимание, что вам, вероятно, потребуется много запросов для сбора достаточного количества данных, чтобы эти предложения были полезными.

Ответ 3

Я бы предпочел использовать для этого уже существующее решение.

Aspell с пользовательский словарь названий может быть хорошо подходит для этого. Генерация словарного файла будет предварительно вычислять всю информацию, необходимую для быстрого предоставления предложений.

Ответ 4

Это старая проблема, DWIM (Do What я Mean), классно реализованный на Xerox Alto Уорреном Тейтельманом. Если ваша проблема основана на произношении, вот обзорная статья, которая может помочь:

J. Zobel и P. Dart, "Фонетическое соответствие строк: уроки из информационного поиска", Proc. 19-й Ежегодный Интер. ACM SIGIR Conf. по исследованиям и разработкам в области информационного поиска (SIGIR'96), август 1996 г., стр. 166-172.

Мне сказали мои друзья, которые работают в поиске информации, что Soundex, описанный Кнутом, теперь считается очень устаревшим.

Ответ 5

Просто используйте Solr или аналогичный поисковый сервер, и тогда вам не обязательно быть экспертом в этом вопросе. Со списком орфографических предложений выполните поиск с каждым предлагаемым результатом, а если есть больше результатов, чем текущий поисковый запрос, добавьте это как результат "вы имели в виду". (Это предотвращает фальшивые орфографические предложения, которые фактически не возвращают больше соответствующих обращений.) Таким образом, вам не нужно собирать много данных, чтобы сделать первоначальное предложение "вы имели в виду", хотя у Solr есть механизмы, с помощью которых вы может вручную настроить результаты определенных запросов.

Как правило, вы не будете использовать RDBMS для этого типа поиска, вместо этого в зависимости от доступных только для чтения, слегка устаревших баз данных, предназначенных для этой цели. (Solr добавляет дружественный интерфейс программирования и конфигурацию к базовому движку Lucene и базе данных.) На веб-сайте для компании, в которой я работаю, ночной сервис выбирает измененные записи из РСУБД и подталкивает их как документы в Solr. С очень небольшим усилием у нас есть система, в которой окно поиска может очень эффективно искать товары, отзывы клиентов, страницы веб-сайта и записи в блоге и предлагать варианты орфографических предложений в результатах поиска, а также граненый просмотр, например, вы видите в NewEgg, Netflix или Home Depot с очень небольшим добавлением нагрузки на сервер (в частности, СУБД). (Я считаю, что Zappo [новый сайт] и Netflix используют Solr внутренне, но не цитируйте меня на этом.)

В вашем сценарии вы будете заполнять индекс Solr списком имен и выбирать соответствующий файл соответствия в файле конфигурации.

Ответ 6

Как и в одном из ответов на вопрос, который вы ссылаетесь, Peter Norvig отличное решение будет работать для этого, в комплекте с кодом Python. Google, вероятно, делает запрос предложений несколькими способами, но то, что у них есть для них, - это много данных. Разумеется, они могут работать с пользовательским поведением модели с огромными журналами запросов, но они также могут просто использовать текстовые данные, чтобы найти наиболее вероятное правильное написание слова, посмотрев, какая коррекция более распространена. Слово someting не отображается в словаре, и хотя это распространенная орфографическая ошибка, правильное написание гораздо более распространено. Когда вы найдете похожие слова, вы хотите, чтобы слово было самым близким к орфографическому и наиболее вероятному в данном контексте.

Решение Norvig состоит в том, чтобы взять кусок нескольких книг из Project Gutenberg и подсчитать слова, которые происходят. Из этих слов он создает словарь, где вы также можете оценить вероятность слова (COUNT(word) / COUNT(all words)). Если вы храните это все как прямой хеш, доступ выполняется быстро, но хранилище может стать проблемой, поэтому вы также можете использовать такие вещи, как суффиксы, Время доступа по-прежнему остается неизменным (если вы реализуете его на основе хэша), но требования к хранилищу могут быть намного меньше.

Затем он генерирует простые изменения для слова с ошибкой (путем удаления, добавления или замены буквы), а затем сдерживает список возможностей, используя словарь из корпуса. Это основано на идее дистанции редактирования (например, расстояние Левенштейна), с простой эвристикой, которая имеет большинство орфографических ошибок с расстоянием редактирования 2 или менее. Вы можете расширить его, так как ваши потребности и вычислительная сила диктуют.

Как только у него есть возможные слова, он находит наиболее вероятное слово из корпуса, и это ваше предложение. Есть много вещей, которые вы можете добавить для улучшения модели. Например, вы также можете настроить вероятность, рассматривая расстояние клавиатуры букв в орфографической ошибке. Конечно, предполагается, что пользователь использует клавиатуру QWERTY на английском языке. Например, перенос e и a q более вероятен, чем перенос e и l.

Ответ 7

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

Что касается поиска, если вы хотите перевернуть свой собственный, а не использовать Aspell или какую-либо другую интеллектуальную структуру данных... предварительные вычисления возможных совпадений - это O (n ^ 2), в наивном случае, но мы знаем для того, чтобы соответствовать друг другу, они должны иметь перекрытие "фонемы" или даже два. Этот шаг предварительной индексации (который имеет низкую ложноположительную скорость) может значительно снизить сложность (в практическом случае что-то вроде O (30 ^ 2 * k ^ 2), где k равно < lt; n),

Ответ 8

У вас есть две возможные проблемы, которые вам необходимо решить (или не адрес, если вы так решите)

Пользователь вводит слово (алгоритм редактирования расстояния)
Пользователи, не зная слова и угадывания (алгоритм фонетического соответствия)

Заинтересованы ли вы в обоих, или только в одном или другом? Они действительно две разные вещи; например Шон и Шон звучат одинаково, но имеют расстояние редактирования 3 - слишком высокое, чтобы считаться опечаткой.

Вы должны предварительно проиндексировать количество слов, чтобы убедиться, что вы предлагаете только соответствующие ответы (похожие на предложение ealdent). Например, если бы я ввел sith, я мог бы спросить, имею ли я значение smith, однако если бы я набрал smith, не было бы смысла предлагать sith. Определите алгоритм, который измеряет относительное правдоподобие слова и предлагает только более вероятные слова.

Мой опыт в параллельном подкреплении упрощал простое, но важное обучение - выполняйте столько уровней индексирования/сита, сколько вам нужно, и не бойтесь включать более 2 или 3. Извлеките все, что не начинается с правильного письмо, например, затем отбирать все, что не заканчивается правильной буквой, и так далее. Вы действительно хотите выполнить расчет расстояний редактирования на минимально возможном наборе данных, поскольку это очень интенсивная операция.

Итак, если у вас есть O (n), O (nlogn) и O (n ^ 2) алгоритм - выполните все три в этом порядке, чтобы убедиться, что вы только положили свои "хорошие перспективы" на ваш тяжелый алгоритм.