Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 11.11.2004, 10:10   #1
Авик
 
CyberJoe's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 30
Posts: 1,348
Downloads: 2
Uploads: 0
Reputation: 9 | 0
Question Сравнивание Стрингов

Вобщем требуется мне алгоритм функции которая будет получать в качестве параметров, два стринга, и возвращать цифру их "похожести"
в процентном соотношении, ну типа хотя бы алгоритм.
Reply With Quote
Old 11.11.2004, 13:08   #2
панаехавший
 
Obelix's Avatar
 
Join Date: 06 2003
Location: форпост
Age: 30
Posts: 4,007
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Детка, ты определись, что ты понимаешь под похожестью? Есть понятие расстояния стрингов (дасиц кич трнеир киманаир), этого тебе нада?
Reply With Quote
Old 11.11.2004, 13:13   #3
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

например strcmp 0 если совсем похожи 1/-1 ежели одна меньше/больше другой.А фактически да - скажи параметр похожести, там придумаем, что надо.
Reply With Quote
Old 11.11.2004, 13:51   #4
Авик
 
CyberJoe's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 30
Posts: 1,348
Downloads: 2
Uploads: 0
Reputation: 9 | 0
Default

Ну как бы сказать вам.
Вот есть у меня несколько прайс листов с наименованиями лекарств.
Но в каждом прайсе все написанно по разному, для примера:
анальгин 25, Анальгин 25, Анальгин. 25., Анальгин mg25, Анальгин 25 мг.
и.т.д
Так вот мне надо как бы ну опознать "Анальгины", Аспирины и всякую мурню.
Reply With Quote
Old 11.11.2004, 13:52   #5
Авик
 
CyberJoe's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 30
Posts: 1,348
Downloads: 2
Uploads: 0
Reputation: 9 | 0
Default

И я не могу юзать strcomp, так как не на C++ вояю, так что алгоритм бы.
Reply With Quote
Old 11.11.2004, 13:58   #6
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

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

Last edited by Agregat; 11.11.2004 at 14:27.
Reply With Quote
Old 11.11.2004, 14:23   #7
Главный Лысый
 
Pascal's Avatar
 
Join Date: 10 2001
Location: AM
Age: 39
Posts: 2,829
Downloads: 4
Uploads: 0
Reputation: 28 | 4
Default Если используется MYSql

Я подозреваю, что надо смотреть в направлении либо:
Quote:
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.
Reply With Quote
Old 11.11.2004, 15:45   #8
Авик
 
CyberJoe's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 30
Posts: 1,348
Downloads: 2
Uploads: 0
Reputation: 9 | 0
Default

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

???

Да и Алгоритм должен быть быстрым, ведь таких стрингов будет 10000.
Reply With Quote
Old 11.11.2004, 16:21   #9
панаехавший
 
Obelix's Avatar
 
Join Date: 06 2003
Location: форпост
Age: 30
Posts: 4,007
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Quote:
Originally Posted by CyberJoe
А Если будет так:
Aspirin 25mg
25mg Aspirin

???

Да и Алгоритм должен быть быстрым, ведь таких стрингов будет 10000.
Может тебе еще исскуственный интеллект?
Reply With Quote
Old 11.11.2004, 16:24   #10
Дошкольник
 
Join Date: 08 2004
Location: Oxford
Age: 38
Posts: 141
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

В биоинформатике есть понятие - sequence alignment. Алгоритмы Needleman-Wunsch (global SA), Smith-Waterman (local SA)
Reply With Quote
Old 11.11.2004, 16:29   #11
Авик
 
CyberJoe's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 30
Posts: 1,348
Downloads: 2
Uploads: 0
Reputation: 9 | 0
Default

Quote:
Originally Posted by Obelix
Может тебе еще исскуственный интеллект?
Ну если тебе не сложно
ДА ладно, все же не так это сложно, (зато сколько дадут бабосов)
Reply With Quote
Old 11.11.2004, 16:38   #12
Главный Лысый
 
Pascal's Avatar
 
Join Date: 10 2001
Location: AM
Age: 39
Posts: 2,829
Downloads: 4
Uploads: 0
Reputation: 28 | 4
Default

Quote:
Originally Posted by CyberJoe
А Если будет так:
Aspirin 25mg
25mg Aspirin

???

Да и Алгоритм должен быть быстрым, ведь таких стрингов будет 10000.
Full-text search v mysql bystriy.
I tvoi primery budut naydeny.
Reply With Quote
Old 11.11.2004, 16:45   #13
Главный Лысый
 
Pascal's Avatar
 
Join Date: 10 2001
Location: AM
Age: 39
Posts: 2,829
Downloads: 4
Uploads: 0
Reputation: 28 | 4
Default

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"
Reply With Quote
Old 11.11.2004, 16:53   #14
Авик
 
CyberJoe's Avatar
 
Join Date: 07 2002
Location: Yerevan
Age: 30
Posts: 1,348
Downloads: 2
Uploads: 0
Reputation: 9 | 0
Default

Думаю может просто сделать базу из всех имен вручную, а потом уже просто ее юзать...
но сделать базу из 1000 наименований... мдя...
Reply With Quote
Old 11.11.2004, 18:02   #15
Painfully Outlandish
 
gaglik's Avatar
 
Join Date: 05 2003
Location: Albainn
Age: 37
Posts: 113
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

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.
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 18:53.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.