Как Google & ldquo; Вы имели в виду? & Rdquo; Алгоритм работы?
Используя приведенные ниже функции, вы можете получить следующие и предыдущие КЛЮЧИ массива. Если текущий ключ недействителен или это последний ( первый - для prev) [] в массиве, затем:
- функция getNext (...) возвращает 0 (первый элемент key )
- Функция getPrev (...) возвращает клавишу последнего элемента массива
Функции циклические.
function getNext(&$array, $curr_key)
{
$next = 0;
reset($array);
do
{
$tmp_key = key($array);
$res = next($array);
} while ( ($tmp_key != $curr_key) && $res );
if( $res )
{
$next = key($array);
}
return $next;
}
function getPrev(&$array, $curr_key)
{
end($array);
$prev = key($array);
do
{
$tmp_key = key($array);
$res = prev($array);
} while ( ($tmp_key != $curr_key) && $res );
if( $res )
{
$prev = key($array);
}
return $prev;
}
14 ответов
Вот объяснение непосредственно из источника [(почти) 115]
Поиск 101!
в минимальное 22:03
Стоящий наблюдения!
В основном и по словам Douglas Merrill бывший технический директор Google это похоже на это:
1) Вы пишете слово (с орфографической ошибкой) в Google
2), Вы не находите то, что Вы хотели (не нажимайте ни на какие результаты)
3) Вы понимаете орфографическую ошибку слова, таким образом, Вы переписываете слово в поле поиска.
4) Вы находите то, что Вы хотите (Вы нажимаете в первых ссылках)
, Этот шаблон умножил миллионы времен, шоу, что наиболее распространено, пишут c орфографическими ошибками и что является самыми "общими" исправлениями.
Этот путь Google может почти мгновенно, исправление написания предложения на каждом языке.
Также это означает, начинают ли в течение ночи все записывать ночь, поскольку "nigth" Google предложил бы то слово вместо этого.
РЕДАКТИРОВАНИЕ
@ThomasRutter: Douglas описывает его как "статистическое машинное обучение".
Они знают, кто исправляет запрос, потому что они знают, какой запрос прибывает, от которого пользователя (использующий cookie)
Если пользователи выполняют запрос, и только 10% пользователей нажимают на результат, и 90% возвращается, и введите другой запрос (с исправленным словом) и на этот раз что 90% нажимают на результат, тогда они знают, что нашли исправление.
Они могут также знать, являются ли те "связанными" запросами двух различных, потому что у них есть информация всех ссылок, которые они показывают.
, Кроме того, они теперь включают контекст в проверку написания, таким образом, они могут даже предложить различное слово в зависимости от контекста.
Видят этот демонстрация волны Google (06 на 44 м), который показывает, как контекст принят во внимание для автоматического исправления написания.
Здесь объяснено, как та обработка естественного языка работает.
И наконец вот потрясающая демонстрация того, что может быть сделано, добавив автоматический машинный перевод (1:12:47) к соединению.
я добавил привязки минуты и секунд к видео, чтобы непосредственно перейти к содержанию, если они не работают, попытайтесь перезагрузить страницу или прокрутить вручную к метке.
Самый легкий способ понять его к динамическому программированию Google.
Это - алгоритм, это было одолжено от Информационного поиска и используется в большой степени в современной дневной биоинформатике, чтобы видеть, как similiar две последовательности генов.
Оптимальное решение использует динамическое программирование и рекурсию.
Это - очень решенная проблема с большим количеством решений. Просто Google вокруг, пока Вы не находите некоторый открытый исходный код.
относительно Вашего вопроса, как подражать поведению, не имея тонн данных - почему бы не использовать тонны данных, собранных Google? Загрузите Google sarch результаты для , слово с ошибками и поиск "Сделало Вы имеете в виду": в HTML.
я предполагаю, что это назвало мэшап в наше время:-)
Я видел что-то на этом несколько лет назад, так, возможно, изменился с тех пор, но по-видимому они запустили его путем анализа их журналов для тех же пользователей, отправляющих очень похожие запросы за короткий промежуток времени, и использовали машинное обучение на основе того, как пользователи исправили себя.
Как предположение... это могло
- поиск слов
- , если это не найдено, используют некоторый алгоритм, чтобы попытаться "предположить" слово.
Могло быть что-то от AI как сеть Хопфилда или сеть обратного распространения или что-то еще "идентификация цифровых отпечатков", восстановив поврежденные данные или исправления орфографических ошибок, как Davide уже упомянул...
Простой. Они имеют тонны из данных. У них есть статистика для каждого возможного термина, на основе того, как часто это запрашивается, и какие изменения его обычно приводят к результатам, которые пользователи нажимают... так, когда они видят, что Вы ввели частую орфографическую ошибку для критерия поиска, они идут вперед и предлагают более обычный ответ.
На самом деле, если орфографическая ошибка является в действительности самым частым искавшим словом, алгоритм возьмет его для правильного.
Google, по-видимому, предлагает запросы с лучшими результатами, не с теми, которые записаны правильно. Но в этом случае, вероятно, корректор написания был бы более выполнимым, Конечно, Вы могли сохранить некоторое значение для каждого запроса, на основе некоторой метрики того, как хорошие результаты это возвращается.
Так,
-
Вам нужен словарь (английский язык, или на основе Ваших данных)
-
Генерируют решетку слова и вычисляют вероятности для переходов с помощью словаря.
-
Добавляют декодер для вычисления минимального ошибочного расстояния с помощью решетки. Конечно, необходимо заботиться о вставках и удалениях при вычислении расстояний. Забавная вещь состоит в том, что QWERTY-клавиатура максимизирует расстояние при нажатии клавиш друг близко к другу. (cae повернул бы автомобиль, риф повернет кошку)
-
Возврат слово, которое имеет минимальное расстояние.
-
Тогда Вы могли сравнить это со своей базой данных запроса и проверить, существуют ли лучшие результаты для других близких соответствий.
Мое предположение - то, что они используют комбинацию расстояние Левенштейна алгоритм и массы данных, которые они собирают относительно поисков, которые запущены. Они могли вытянуть ряд поисков, которые имеют самое короткое расстояние Левенштейна из вводимой строки поиска, затем выбирают ту с большинством результатов.
Хм... Я думал, что Google использовал их обширный корпус данных (Интернет), чтобы сделать некоторую серьезную обработку естественного языка (Обработка естественного языка).
, Например, у них есть так много данных из всего Интернета, что они могут считать количество раз, три последовательности слов происходят (известный как триграмма ). Таким образом, если они видят предложение как: "розовый frugr концерт", они видели его, имеет немного хитов, затем найдите наиболее вероятный "розовый * концерт" в их корпусе.
Они, по-видимому, просто делают изменение того, что Davide Gualano говорил, тем не менее, так определенно читает ту ссылку. Google действительно, конечно, использует все веб-страницы, которые он знает как корпус, так, чтобы сделал его алгоритм особенно эффективным.
Я нашел эту статью некоторое время назад: , Как Записать Орфографический корректор , записанный Peter Norvig (директор по исследованиям в Google Inc.).
Это - интересное чтение о теме "исправления орфографических ошибок". Примеры находятся в Python, но это ясно и просто понять, и я думаю, что алгоритм может быть легко переведен в другие языки.
Ниже следует краткому описанию алгоритма. Алгоритм состоит из двух шагов, подготовки и проверки слова.
Шаг 1: Подготовка - установка базы данных слова
Лучший состоит в том, если можно использовать фактические поисковые слова и их происшествие. Если у Вас нет этого, большой набор текста может использоваться вместо этого. Считайте возникновение (популярность) каждого слова.
Шаг 2. Проверка Word - нахождение слов, которые подобны тому, проверило
Подобный, означает, что расстояние редактирования является низким (обычно 0-1 или 0-2). Расстояние редактирования является минимальным количеством, вставляет/удаляет/изменяет/подкачивает, должен был преобразовать одно слово другому.
Выбирают самое популярное слово из предыдущего шага и предлагают его в качестве исправления (если кроме самого слова).
Для теории "сделал Вы имеете в виду" алгоритм, который можно отослать к Главе 3 Введения в Информационный поиск. Это доступно онлайн бесплатно. Раздел 3.3 (страница 52) точно отвечает на Ваш вопрос. И конкретно ответить на Ваше обновление Вам только нужен словарь слов и ничего иного (включая миллионы пользователей).
Обычно корректор правописания в производстве использует несколько методологий для предоставления правописания. Вот некоторые из них:
Определите способ определения необходимости исправления орфографии. К ним могут относиться недостаточные результаты, результаты, которые не являются конкретными или недостаточно точными (в соответствии с какой-то мерой) и т. Д. Затем:
Используйте большую часть текста или словарь, в котором, как известно, все или большинство написаны правильно. Их легко найти в Интернете, в таких местах, как LingPipe . Затем, чтобы определить лучшее предложение, вы ищите слово, которое наиболее близко соответствует нескольким показателям. Самый интуитивный из них - похожие персонажи. В ходе исследований и экспериментов было доказано, что совпадение последовательности из двух или трех символов работает лучше. (биграммы и триграммы). Для дальнейшего улучшения результатов взвесьте более высокий балл по совпадению в начале или конце слова. Из соображений производительности индексируйте все эти слова как триграммы или биграммы, чтобы при выполнении поиска вы преобразовывали его в n-грамм и выполняли поиск с помощью хеш-таблицы или trie.
Используйте эвристику, связанную с возможными ошибками клавиатуры, основанными на расположении символов , Так что «hwllo» должно быть «привет», потому что «w» близко к «e».
Используйте фонетический ключ (Soundex, Metaphone) для индексации слов и поиска возможных исправлений. На практике это обычно возвращает худшие результаты, чем при использовании индексации по n-граммам, как описано выше.
В каждом случае вы должны выбрать лучшую коррекцию из списка. Это может быть метрика расстояния, такая как левенштейн, метрика клавиатуры и т. Д.
Для фразы из нескольких слов может быть написано только одно слово, в этом случае вы можете использовать оставшиеся слова в качестве контекста при определении наилучшего соответствия.
Существует особая структура данных - троичное дерево поиска , которое, естественно, поддерживает частичные совпадения и совпадения ближайшего соседа.
Используйте расстояние Левенштейна , затем создайте дерево показателей (или тонкое дерево) для индексации слов. Затем выполните запрос 1-ближайшего соседа, и вы получите результат.