Правописание альтернативы на основе базы данных?

Question

Я ищу эффективный способ (использование PHP с базой данных Mysql), чтобы предложить альтернативное написание для запроса.

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

Например: пользователь должен заполнить форму с полем "Город", и я хочу убедиться, что все будут использовать одинаковое правописание для указанного города, (поэтому я не получаю заполнение людьми " Питсбург ", когда они имеют в виду" Питтсбург ").

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

Какой-нибудь алгоритм, учебные пособия или идеи о том, как этого добиться?

Answer 1

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

вот псевдокод для алгоритма ( из Википедии ):

int LevenshteinDistance(char s[1..m], char t[1..n])
   // d is a table with m+1 rows and n+1 columns
   declare int d[0..m, 0..n]

   for i from 0 to m
       d[i, 0] := i
   for j from 0 to n
       d[0, j] := j

   for i from 1 to m
       for j from 1 to n
       {
           if s[i] = t[j] then cost := 0
                          else cost := 1
           d[i, j] := minimum(
                                d[i-1, j] + 1,     // deletion
                                d[i, j-1] + 1,     // insertion
                                d[i-1, j-1] + cost   // substitution
                            )
       }

   return d[m, n]

и здесь вы можете найти реализацию real для всех видов языков: http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance

Answer 2

Я использовал пакет pspell http://uk.php.net/pspell для этого. Возьмите поисковый запрос, проверьте орфографию. Если это не в порядке, PSPELL сделает предложения.

Вы даже можете запустить предложения через поиск, сосчитать результаты и сказать: «Ваш поиск по запросу« foo »дал 0 результатов. Вы имели в виду "baz" (12 результатов) или "bar" (3 результата).

Если вы беспокоитесь о производительности, делайте это только тогда, когда поиск возвращает 0 результатов.

Answer 3

Может быть, это поможет http://jquery.bassistance.de/autocomplete/demo/ Он использует JQuery (на стороне клиента) и php (на стороне сервера). Пример подается из массива, но его можно легко изменить, чтобы он использовал базу данных MySQL.

Answer 4

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

Answer 5

Я бы сделал это в соответствии с типами пользователей и предложил бы по префиксу (аля Google Suggest). A trie было бы неплохо для этого. Это не поможет исправить первые буквы с ошибками, но это довольно редко.

Answer 6

Я считаю, SoundEx лучше, чем расстояние Левенштейна.

SoundEx - это функция, которая генерирует хэш слова / фразы на основе звука, который он издает на английском языке. Он отлично помогает людям, которые не умеют писать, соответствуют каноническому написанию.

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

SoundEx встроен в MySql. Вот один урок по его использованию .

Answer 7

Посмотрите на Примеры Javascript В нем перечислены 13 различных кодов полей автозаполнения.

Я использовал нечто похожее на одном из своих сайтов, по сути, у меня есть слой div, настроенный под текстовым полем, когда пользователь вводит этот запрос HTTP на основе Ajax в мой скрипт SQL-запроса, который обновляет каждую букву, которую они тип. Div обновляется любыми подходящими записями в БД, по которым пользователь может щелкнуть, чтобы выбрать.

Answer 8

Пожалуйста, взгляните на Yahoo! Компонент автозаполнения библиотеки пользовательского интерфейса . Я думаю, что это именно то, что вы ищете. В разделе «Использование источников данных» объясняется, как использовать источники данных различного типа, включая серверные, такие как у вас.