Сравнивание Стрингов

[CyberJoe]

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

[Obelix]

Детка, ты определись, что ты понимаешь под похожестью? Есть понятие расстояния стрингов (дасиц кич трнеир киманаир), этого тебе нада?

[Agregat]

например strcmp :) 0 если совсем похожи 1/-1 ежели одна меньше/больше другой.А фактически да - скажи параметр похожести, там придумаем, что надо.

[CyberJoe]

Ну как бы сказать вам.
Вот есть у меня несколько прайс листов с наименованиями лекарств.
Но в каждом прайсе все написанно по разному, для примера:
анальгин 25, Анальгин 25, Анальгин. 25., Анальгин mg25, Анальгин 25 мг.
и.т.д
Так вот мне надо как бы ну опознать "Анальгины", Аспирины и всякую мурню.

[CyberJoe]

И я не могу юзать strcomp, так как не на C++ вояю, так что алгоритм бы.

[Agregat]

lstrcmp(i) - системные функции виндоза.
0. Sum = 0;
1. по очереди проходишь по всем символам сравниваешь их , если равны + 2. если равны, но без учета регистра +1 (тут я поправил)
3. пробелы не сравниваешь вообще - пропускаешь (пробел, верт и гор
табуляция, перевод строки, возврат каретки)
4. несовпадения вычитаешь :)
смотришь число...
или же:
берешь и ищещь слова из одной строки в другой без учета регистра... похожесть сумма похожих чисел чем больше тем лучше...

[Pascal]

Я подозреваю, что надо смотреть в направлении либо:

SOUNDEX(str) Returns a soundex string from str. Two strings that sound almost the same should have identical soundex strings. A standard soundex string is four characters long, but the SOUNDEX() function returns an arbitrarily long string. You can use SUBSTRING() on the result to get a standard soundex string. All non-alphabetic characters are ignored in the given string. All international alphabetic characters outside the A-Z range are treated as vowels. mysql> SELECT SOUNDEX('Hello');
-> 'H400'
mysql> SELECT SOUNDEX('Quadratically');
-> 'Q36324'
Note: This function implements the original Soundex algorithm, not the more popular enhanced version (also described by D. Knuth). The difference is that original version discards vowels first and then duplicates, whereas the enhanced version discards duplicates first and then vowels.
Либо смотреть здесь http://dev.mysql.com/doc/mysql/en/Fulltext_Search.html на предмет Score.

[CyberJoe]

А Если будет так:
Aspirin 25mg
25mg Aspirin

???

Да и Алгоритм должен быть быстрым, ведь таких стрингов будет 10000.

[Obelix]

А Если будет так:
Aspirin 25mg
25mg Aspirin

???

Да и Алгоритм должен быть быстрым, ведь таких стрингов будет 10000.
Может тебе еще исскуственный интеллект?

[Ablertus]

В биоинформатике есть понятие - sequence alignment. Алгоритмы Needleman-Wunsch (global SA), Smith-Waterman (local SA)

[CyberJoe]

Может тебе еще исскуственный интеллект?
Ну если тебе не сложно :D
ДА ладно, все же не так это сложно, (зато сколько дадут бабосов)

[Pascal]

А Если будет так:
Aspirin 25mg
25mg Aspirin

???

Да и Алгоритм должен быть быстрым, ведь таких стрингов будет 10000. Full-text search v mysql bystriy.
I tvoi primery budut naydeny.

[Pascal]

Odnako ideala ty vse ravno ne naydesh - poetomu stoit predusmotret' nekiy variant opredeleniya etikh parametrov vruchnuyu.
I tol'ko posle etogo nachat' sravnivat' realizatsii na "zhivykh sluchayakh"

[CyberJoe]

Думаю может просто сделать базу из всех имен вручную, а потом уже просто ее юзать...
но сделать базу из 1000 наименований... мдя...

[gaglik]

you can use a dynamic programming algorithm to find the longest common substring (I think ignoring cases and spaces might be a good idea), then in the aspirin example you'll find "aspirin".
I think this will do the main part of the work.

[Agregat]

Может тебе еще исскуственный интеллект?
надо смотреть именно в этом направлении.

[analyst]

Че Ав джан, чстацвав, ВБ-ум исскуственни интелекты компонент чка ашкис....

[Obelix]

>Agregat
Хе, молодежь наставляешь :D

>analyst
Դե դեռ հույս կա որ API ում տենց ֆունկցիա ըլնի:

[CyberJoe]

>analyst
Де нсти модули гри. я тебя доллар дам :P

[Agregat]

>analyst
Де нсти модули гри. я тебя доллар дам :Pэх... молодежь пошла книжет не читает.

[Вирус]

я думаю имеет смысл сравнивать не символы а последовательности без учета регистра, пробелов и т.д.. Этот алгоритм конечно будет ворочаться дольше простого посимвольного сравнения, но, иногда цель оправдывает средства.

[CyberJoe]

А если так.
Просто взять все слова из текста, и сравнивать их со словами из другого текста, без учета очередности слов, регистра, точек, и пробелов.
тогда:
Analgin 10mg N50
и
ANALGIN N50 10MG
будут идентичны.

[Agregat]

А если так.
Просто взять все слова из текста, и сравнивать их со словами из другого текста, без учета очередности слов, регистра, точек, и пробелов.
тогда:
Analgin 10mg N50
и
ANALGIN N50 10MG
будут идентичны.ТОгда можно сделать по другому
получить массивы слов из первой и второй строчки. отсортировать их и сравнивать. при этом можно сравнивать двояко - учитывая регистр и не учитывая. Если совпадают с регистром - это ближе, чем если совпадают без регистра. Итак. Для каждого слова из первого (уже отсортированного массива) находим его место во втором массиве - сравниваем с элементами на данной позиции: если слова равны +2, если равны без учета регистра +1, если такого слова нет -1 или 0. Потом для всех неиспользованных слов из второго массива -1 или 0. Чем больше число тем похоже строки

[CyberJoe]

Это уже дело :)

[Agregat]

Это уже дело :)Одного, я не понимаю, почему я за тебя должен думать. ПОделишься баблом.

[CyberJoe]

Я не жадный, будет бабло, поделюсь.

[Н.К.Рерих]

Не люблю я стринги! :)

[Obelix]

Не люблю я стринги! :)
Особенно Си стринги, чэ? Я тоже их не люблю.

[Н.К.Рерих]

Ага!

[Agregat]

Чят закончили.

[[ Xelgen ]]

Чят закончили.
..раз уж сделка не состоялаcь? :)

Аво, верджы дра такиц вонц дурс екар?

[CyberJoe]

Xelgen>Я написал отдельную прогу в которая составила моими руками.
Базу типа
Аспырын Асяприн Аспутин 1
Анальгин Анылгин анальгин 2
... и.т.д

а потом прогу которая с ютой базой работала, оказалось что комбинаций в прайс листах только 14 атк что на каждое лекарство по 14 вариантов.... вот так вот