Перейти к содержимому

Фото
- - - - -

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


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

#1 StrikeR

StrikeR

    бугога

  • Постоялец
  • 778 сообщений
  • Откуда:QLD. Australia

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

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

#2 sideways

sideways

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

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

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

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

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

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

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

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


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

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

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

#3 Setor

Setor
  • Постоялец
  • 1 890 сообщений
  • Откуда:Эстония, Таллин

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

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

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

#4 Акей

Акей

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

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

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

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

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

#5 ParadoxL

ParadoxL
  • Постоялец
  • 4 756 сообщений
  • Откуда:Edinburg

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

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

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

http://www-igm.univ-...ring/node6.html
  • 0
Victoria nulla est, Quam quae confessos animo quoque subjugat hostes ...
Верю в смерть после жизни, любовь после секса и в крем после бритья ...

#6 StrikeR

StrikeR

    бугога

  • Постоялец
  • 778 сообщений
  • Откуда:QLD. Australia

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

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

#7 ParadoxL

ParadoxL
  • Постоялец
  • 4 756 сообщений
  • Откуда:Edinburg

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

Акей, алгоритм Левенштейна очень медленный ...
  • 0
Victoria nulla est, Quam quae confessos animo quoque subjugat hostes ...
Верю в смерть после жизни, любовь после секса и в крем после бритья ...

#8 zedirtybastard

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

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

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

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

  • 0

#9 Акей

Акей

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

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

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

Incubo, да, но зато бери и используй:) Может у автора объемы информации небольшие
  • 0

#10 sideways

sideways

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

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

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

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

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

  • 0

#11 Setor

Setor
  • Постоялец
  • 1 890 сообщений
  • Откуда:Эстония, Таллин

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

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

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

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

Бывает)
  • 0

#12 zedirtybastard

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

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

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

#13 Setor

Setor
  • Постоялец
  • 1 890 сообщений
  • Откуда:Эстония, Таллин

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

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

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

#14 StrikeR

StrikeR

    бугога

  • Постоялец
  • 778 сообщений
  • Откуда:QLD. Australia

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

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

#15 Setor

Setor
  • Постоялец
  • 1 890 сообщений
  • Откуда:Эстония, Таллин

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

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

#16 ParadoxL

ParadoxL
  • Постоялец
  • 4 756 сообщений
  • Откуда:Edinburg

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

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

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

#17 StrikeR

StrikeR

    бугога

  • Постоялец
  • 778 сообщений
  • Откуда:QLD. Australia

Отправлено 27 Февраль 2008 - 17:02

Setor, ну ок, облажал малёх, не указал, что да, понадобится пхп, который передаст мне все строчки из базы:) но для начала можно обойтись и массивом в 10 слов, что бы протестить

Сообщение изменено: StrikeR (27 Февраль 2008 - 18:00 )

  • 0

#18 Setor

Setor
  • Постоялец
  • 1 890 сообщений
  • Откуда:Эстония, Таллин

Отправлено 27 Февраль 2008 - 17:09

но для начала можно обойтись и массивом в 10 слов, что бы протестить

Две вечные проблемы:
1) На 10 строчках работает хорошо, пусть работает.. Когда будет 100 строк и на клиенте подвиснит флеш что будешь делать? :)
2) На самом деле в базе не будет больше 100 строк, но планируют сразу на миллион ;)

P.S. я бы написал хранимку по алгоритму, предложенному Incubo
  • 0