Нечёткий поиск на клиенте и Soundex

[@GeniyZ]

спасибо огромное — обязательно попробую сегодня вечером завести это дело на Node.JS+express+postgres и если хорошо заведётся, то обязательно заиспользую на очередном Node.JS проекте =)))
А то для Node.js вообще нормальных движков поиска нет, а с такими вкусняшками — так тем более =))

[@javascript]

Пожалуйста! Мне дико интересно, что получится.
Если будут вопросы или ошибки — пишите, будем допиливать вместе :-)

[@aleks_raiden]

буквально вчера вроде созданный — github.com/visionmedia/reds

[@no_smoking]

Очень здорово надо будет попробовать.
По чему то не ищет по слову «Барселона» хотя есть отель «Hotel Barcelona Universal»

[@javascript]

Потому что «Барселона» = «Barselona», а «Barcelona» = «Барцелона».

Спасибо за баг, буду думать как исправить!

[@no_smoking]

Может сделать при транслите с и s равнозначными

[@EndUser]

Нет, нельзя: гуччи, цеппелин и т.д.

С брендами грабли в том, что половина от неанглийских названий, фамилий…

Надо отдельное исследование, наверное

[@javascript]

Да, это непростая проблема.

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

[@Doggy]

добавить WikiPedia: Расстояние_Левенштейна

(ссылки не дает постить)

[@Doggy]

Есть своя быстрая реализация на scala, могу на яваскрипт переписать — посмотреть скорость если захотите внедрить)

[@javascript]

Очень интересно, давай попробуем!

[@Doggy]

Вот переписал на яваскрипт. Вычисляет расстояние Левенштейна (int)

github.com/Rudogma/JsAlgos/tree/master/levenstein

[@javascript]

github.com/Rudogma/JsAlgos/blob/master/levenstein/levenshtein.js
Немножко недокоммитилось, мне кажется.

[@Doggy]

Докоммитилось)

Сделайте чекаут или edit(там справа)

Это траблы гитхаба с отображением js, хз почему)

[@serebro]

Мне жутко интересно, удалось ли вам «прикрутить» Расстояние Левенштейна к Soundex? Что получилось?

[@Zabatov]

так а в чем прикол-то тогда, если он не дает c на s заменить. Я ведь могу и не знать точного названия. В задачи у вас этот пункт вроде как есть, а в реализации нет. А если я напишу Barselonna или Barselena. Нужен алгоритм, который будет неточности исправлять в словах

[@javascript]

В транслите С = S, а Ц = C.
Поэтому по запросу «Барселона» не находит, а по «Барцелона» находит.

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

[@GeniyZ]

Не стоит прямо так исправлять — всё-таки не баг. Ведь с и ц — совсем разные звуки.
По-итальянски с звучит как «ч». А zz (задвоенное Z) читается как «ц».
Но это же не повод в алгоритме рассматривать ц, с, ч, з,… как один и тот же звук.

[@javascript]

Можно попробовать ввести вероятные варианты и дополнять поиск ими.
А ещё в этом случае появится ранжирование.

Надо попробовать :-)

[@GeniyZ]

Ну вообще да — это наверное единственный способ избежать всех возможных недочётов.
Ведь по существующему алгоритму «Einstein» не будет соответствовать «Айнштайн» как ни крути.
А жаль, ведь именно это является правильным произношением.
Хотя если «налету» определять язык слова и подставлять заранее подготовленную таблицу соответствия звуков…
В вашем случае это возможно — вы можете смотреть на страну отеля и производить поиск по его родному звучанию и по латинизированному.

[@javascript]

По данному алгоритму, 'Айнштайн' = 'Einstein' = '06436', так как это довольно простой случай.
Предлагают использовать расстояние Левенштейна, мне кажется это поможет с Барселоной.

[@tenshi]

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

[@javascript]

Об этом я не думал.
Как может выглядеть в javascript фонемное представление?

[@aroh]

А почему «Radisson» == «Redison» == «9346», если верить статье в вики, то
«Radisson» == «Redison» == «R325»?

Вообще идея на грани гениальности. А может и за гранью -)

[@javascript]

Да, оригинальный алгортим возвращает R325, но данный модифицированный и позволяет не привязываться к первой букве, так как по звучанию H = KH

[@aroh]

А можно подробнее про алгоритм?

[@aroh]

Сорри, нашел его описание в сообщении

[@rednaxi]

Вижу в результатах поиска B-Hotel, ввожу Б-Отель — находит Rafaelhoteles Badalona. Eurostars Grand Marina по запросу евростарс тоже не находит. Также уже заметили проблему с барселоной.

Но в целом конечно работа проделана хорошая и полезная, спасибо за отчет. Осталось только доточить мелочи :)

[@javascript]

Спасибо, буду дотачивать!
Мелочи — это самое важное :-)

[@EugeneBond]

идея хорошая, но без человеческого фактора не осуществимая.
как выше заметил товарищ GeniyZ, те же, к примеру, итальянские названия надо отличать от неитальянских. в случае с отелями можно попытаться отталкнуться от локации отеля, но нет гарантии, что название не французское или английское. + отели это достаточно специфический use case

[@javascript]

К сожалению, мы не знаем на каком языке пользователь вводит запрос.

[@javascript]

Да, с некоторой точностью можно.

[@javascript]

Верно, я находил реализации по-проще:

    function soundex(str, p){
        var i, j, l, r, p = isNaN(p) ? 4 : p > 10 ? 10 : p < 4 ? 4 : p,
        m = {BFPV: 1, CGJKQSXZ: 2, DT: 3, L: 4, MN: 5, R: 6},
        r = (s = str.replace(/[^A-Z]/g, "").split("")).splice(0, 1);
        for(i = -1, l = s.length; ++i < l;)
            for(j in m)
                if(j.indexOf(s[i]) + 1 && r[r.length-1] != m[j] && r.push(m[j]))
                    break;
        
        return r.length > p && (r.length = p), r.join("") + (new Array(p - r.length + 1)).join("0");
    };

Но данная больше оптимизирована под работу с транслитом.

[@seriyPS]

И хоть бы один комментарий в коде…

[@serebro]

Если знаком с JS, то все понятно и без комментов, а в этом блоге таких большинство.

[@azproduction]

Да, хотя бы пример использования написал чтоли… не говорю уж о jsdoc и внешнем репозитории… Раз вы javascript, заняли такой ник, то извольте написать хорошо, блог все-такие ваш теска :)
К реализации алгоритма замечаний нет, к оформлерию да:
1. Почему используется codes: JSON.parse()? Можно использовать объект JavaScript: {"A":{...}}
2. Почему используется конструктор RegExp new RegExp('[Vv\u1d5b]', 'ig'), вместо литерала /[Vv\u1d5b]/ig
3. Использовать словарь (en_ru: : ['A': 'А', 'a': 'а', 'B': 'Б', 'b': 'б'}) вместо параллельных массивов (ru: ['А', 'а', 'Б', 'б'], en: ['A', 'a', 'B', 'b']) для транслитерации в одну сторону (в вашем случае) было бы удобнее и нагляднее

[@javascript]

Огромнейшее спасибо за полезные советы!
Я внёс все правки :-)

[@evalexdy]

Собрался тут переписывать свой старый скрипт для анализа текста и выдергивания из него ключевых слов (по частоте использования) и дай-ка, думаю, пробегусь по хабру, может чего полезного найду.
Спасибо огромное за статью, вместо запланированного дня для экспериментов уложился в 15 минут! Несмотря на то, что SOUNDEX плохо подходит для словоформ, в качестве быстрого решения для заполнения метатега keywords подходит более чем, главное в анализируемом тексте не смешивать русский и английский языки.
Если кому интересно, вот коротенькая реализация на github'е: github.com/evalexdy/Keywords-Generator