Новые публикации

Javascript Disabled Detected

You currently have javascript disabled. Several functions may not work. Please re-enable javascript to access full functionality.

по какому принцепу работает замена слов?

Started By StrikeR, фев 27 2008 01:56

Вы не можете создать новую тему
Please log in to reply

17 ответов в этой теме

#1 StrikeR

бугога

Постоялец
798 сообщений

Откуда:QLD. Australia

Отправлено 27 февраля 2008 - 01:56

Неоднократно все стречали на том же гугле, если неправильно ввести слово, появляется фраза
"возможно, вы имели ввиду ...". Возьмём в пример слово "прИмер", напишу я его через Е - "прЕмер", гугль сразу отреагирует... каким образом он подбирает символы в слово? Есть соображения?

Наверх

#2 sideways

мальчик из трёх букв

Постоялец
1 091 сообщений

Отправлено 27 февраля 2008 - 02:33

Если бы я был разработчиком Гугла, то в простейшем случае я бы сделал такую процедуру:

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

Если же попадается несовпадающая буква, то запускаю эту же самую процедуру (рекурсия), только передаваемым словом будет слово, начиная с n+2 буквы, если n-ная буква была последней совпавшей.

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

Таким образом, на выходе мы получим слово, наиболее похожее на введенное.

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

А там всё это полюбому есть, Гугл не на коленке делался

Кстати, зачем тебе это?

Наверх

#3 Setor

Постоялец
1 890 сообщений

Откуда:Эстония, Таллин

Отправлено 27 февраля 2008 - 06:35

Loader, а тебе не кажется, что это было бы слишком медленно ?)

Хотел было поразмышлять на эту тему, но к сожалению, ничего интересного на ум не лезет, задача достаточно сложная и практически нереализуемая в "домашних условиях". В таких случаях я обычно задаю интересующий меня вопрос гуглю и вот что он об этом думает: http://www.google.ru...eid=navcl...ду"

Наверх

#4 Акей

Смотрит свысока

Постоялец
2 134 сообщений

Отправлено 27 февраля 2008 - 09:11

можно начать с http://ee.php.net/ma...imilar-text.php

или http://ee.php.net/ma...levenshtein.php (эта вроде перформит лучше)

Наверх

#5 ParadoxL

Постоялец
5 023 сообщений

Откуда:Edinburg

Отправлено 27 февраля 2008 - 09:23

StrikeR, короче процес этот называется FuzzyLogic ... советую рассмотреть алгоритм Shift-OR ... реализовывал как то его для одного VCL компонента *Delphi* ... его возможности были найти до трех ошибок в слове и подобрать нужное из базы в 13 000 000 записей менее чем за секунду. Думаю, что гугл пользуется чем-то сродным этому алгоритму.

Вот нашел ... не плохое описание.

http://www-igm.univ-...ring/node6.html

Victoria nulla est, Quam quae confessos animo quoque subjugat hostes ...
Верю в смерть после жизни, любовь после секса и в крем после бритья ...

Наверх

#6 StrikeR

бугога

Постоялец
798 сообщений

Откуда:QLD. Australia

Отправлено 27 февраля 2008 - 11:08

всем спасибо, почитаю всё, что выдали

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

Наверх

#7 ParadoxL

Постоялец
5 023 сообщений

Откуда:Edinburg

Отправлено 27 февраля 2008 - 12:00

Акей, алгоритм Левенштейна очень медленный ...

Victoria nulla est, Quam quae confessos animo quoque subjugat hostes ...
Верю в смерть после жизни, любовь после секса и в крем после бритья ...

Наверх

#8 zedirtybastard

Пользователь
499 сообщений

Отправлено 27 февраля 2008 - 13:01

http://ru.wikipedia.org/wiki/Soundex
Принцип работы: высчитывает код звучания слова для дальнейшего его сравнения с другими ключами. Довольно-таки быстр

Сообщение изменено: zedirtybastard (27 февраля 2008 - 13:04 )

Наверх

#9 Акей

Смотрит свысока

Постоялец
2 134 сообщений

Отправлено 27 февраля 2008 - 13:20

Incubo, да, но зато бери и используй

Может у автора объемы информации небольшие

Наверх

#10 sideways

мальчик из трёх букв

Постоялец
1 091 сообщений

Отправлено 27 февраля 2008 - 13:34

Setor, пардон, щас выспался и стыдно стало за написанное

Сообщение изменено: Loader (27 февраля 2008 - 13:35 )

Наверх

#11 Setor

Постоялец
1 890 сообщений

Откуда:Эстония, Таллин

Отправлено 27 февраля 2008 - 14:09

http://ru.wikipedia.org/wiki/Soundex
Принцип работы: высчитывает код звучания слова для дальнейшего его сравнения с другими ключами. Довольно-таки быстр

Но с русским оно не дружит

Я кстати, тоже о ней подумал в первую очередь.

Setor, пардон, щас выспался и стыдно стало за написанное

Бывает)

Наверх

#12 zedirtybastard

Пользователь
499 сообщений

Отправлено 27 февраля 2008 - 15:25

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

Наверх

#13 Setor

Постоялец
1 890 сообщений

Откуда:Эстония, Таллин

Отправлено 27 февраля 2008 - 15:32

zedirtybastard, я как всегда мыслил глобально

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

Возможно, тогда чел не ошибётся и найдёт нужный ему вариант из списка.

Наверх

#14 StrikeR

бугога

Постоялец
798 сообщений

Откуда:QLD. Australia

Отправлено 27 февраля 2008 - 15:49

Кстати, вариант Loader'а - один из вариантов всё таки, но да, будет слишком медленно работать, при большом объёме слов.
Сейчас не важно на русском будет пользователь писать, или на англиЦком, да хоть на арабском, главное хоть что-то что бы получилось, а дальше уже совершенствовать.
Setor, Для того, что бы сервер делал поиск по запросу, нужно что-то написать для него

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

Наверх

#15 Setor

Постоялец
1 890 сообщений

Откуда:Эстония, Таллин

Отправлено 27 февраля 2008 - 15:52

StrikeR, какую-то странную задачку ты себе придумал, данные, по которым будет идти поиск обычно хранятся в БД, иначе, что это за поиск такой?)))

Наверх

#16 ParadoxL

Постоялец
5 023 сообщений

Откуда:Edinburg

Отправлено 27 февраля 2008 - 15:53

StrikeR, говорю тебе самый шустрый и простой это Shift-OR ... его реализация от начала до конча два часа максимум (с отладкой и добавлением детских обид)