Нечёткий поиск на клиенте и 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