В общем нужна функция которая рассчитывает что-то вроде коэффициента корреляции (похожести) между строками.

Есть:

• каталог правильных названий (названия сложные - 1-4 слова, встречаются цифры, точки слэши, запятые...).
• поставщики, которые ну никак не хотят придерживаться стандартных названий в прайсах. А посему ставят/убирают точки,запятые/слэши, сокращают некот. названия, очепятываются, дают неполные.
• девушки, которые приводят все в соответствие.

Хочется иметь какую-нить функцию со смыслом:

Код

public float correl (String s1, String s2)

значения на выходе - [0;1]. 1 - строки совпадают (м.б. с точностью до регистра), чем ближе к нулю - тем менее строки
похожи.

А обработка примерно следующая - беру название из прайса и сравниваю этой функцией с эталонами. Если есть полное совпадение, то поставщик - молодец, если нет - выдаю список самых похожих эталонов на выбор девушке.

Наиболее простой, ИМХО, вариант использовать регулярные выражения ...

Названия такого рода/состава (и в каталоге и в прайс-листах):

Цитата

90-60-90 0,5 N150 табл 90-60-90 120,0 крем антицеллюлитный туба акваципро 0,2% 100мл р-р д/инф флак аккупро 0,005 N30 табл п/о алпростан 0,0001 0,2мл N10 конц д/инф амп алтайский фиточай N16 противопростудный 2,0 N20 фильтр-пак алфит д/проф леч тромбофлебита 1+2 утро+вечер сбор лек трав алфит д/проф-ки орви 1+2 N30 утро+вечер сбор лек трав комп алфит простатит 1+2 N30 утр0+вечер сбор лек трав

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

Стратегия видится примерно такая:
- toUpperCase()
- убрать пробелы перед запятыми, поставить пробелы после недесятичных запятых
- заменить латинские A, B, C, E, H, K, M, O, P, T, X на русские с таким же начертанием
- \ -> /, нуль -> О, Ё -> Е, Y -> У
- "["']+" -> "", "\\s+" -> " ", "^\\s+" -> "", "\\s+$" -> ""
- теперь String.equals может сказать правду

Если не совпали, работаем дальше
- разбиваем на кусочки: String[] token = name.split("[^,0-9A-ZА-Я]+");
- считаем попарно степень схожести кусочков эталонного названия с кусочками прайсового
- считаем суммарную "схожесть", нормируем.

То как будем нормировать - зависит от ф-ции сравнения кусочков. А вот как их сравнивать..?..

Это сообщение отредактировал(а) Zandr - 22.10.2004, 07:29

Похоже регулярное выражение, для каждой позиции прайса должно быть уникальным
(если не будет найден универсальный алгоритм) в PHP4 была функция sql_regcase() , которая формировала регулярное
выражение на основе входной строки:
http://pl2.php.net/manual/ru/printwn/funct...sql-regcase.php
, может быть разгадка здесь?

Zandr
В Java есть класс для обработки строк. Называется StringTokenizer. Там и куча функций имеется. Описание могу прислать. Оно из MSDN(Visual Studio) и на английском, естественно.
Пиши, если нужно, скопирую и вышлю.

Привет Светлая.
Приятно, что Вы к нам заглянули. Мы тут копим людские ресурсы по JAVA, так что будем всегда рады видеть.
Только по поводу StringTokenizer я не соглашусь. Он же в принципе для разбивки строки на элементы.
split это тоже так делает, только более эффектвино в плане понимания чего делаешь (работать может и медленнее будет).

Добавлено @ 18:44
А нельзя пойти от фонетического совпадения ?
Выписать основные сочетания букв и как они читаются. Хотя может и бред все это.

А не хотите задать этот вопрос в "Алгоритмах" ?

AntonSaburov
Привет, мне тоже очень приятно к вам заглянуть.

По поводу StringTokenizer - я имела ввиду не саму функцию, а весь класс StringTokenizer, в нём есть 6 функций. Я не вникала особо в их описание, но если кто захочет - пишите.

У Апаче.орг - есть для явы парсер регуляр експрешенс - воспользуися им
Синтаксис напоминает перль

http://jakarta.apache.org/regexp/index.html

Цитата

Хотя может и бред все это.

Ни чуть не бывало !

вот прример который сравниват пароли по их звучанию
(правда на Perl )

Код

use Text::Soundex; use User::pwent; print "Lookup user: "; chomp($user =<STDIN>); exit unless defined $user; $name_code = soundex($user); while ($uent = getpwent( )) {    ($firstname, $lastname) = $uent->gecos =~ /(\w+)[^,]*\b(\w+)/;    if ($name_code eq soundex($uent->name) ||        $name_code eq soundex($lastname)   ||        $name_code eq soundex($firstname)  )    {        printf "%s: %s %s\n", $uent->name, $firstname, $lastname;    } }

xaoc2
Нет, не то... Эта вещь полезна когда есть регекспы, но нет (по непонятным причинам) функции сравнения строк без учета регистра.

Светлая
Токенайзер тоже не то Кроме как строчки бить на подстроки его толком-то и не применишь нигде. И все имели в виду именно класс

AntonSaburov
Задам, наверное, в алгоритмах еще На счет фонетической схожести... Тут custom soundex нужно делать.

Bors
Насколько я понимаю - это старый пакет. С 1.4 есть java.util.regex. Он будет использоваться, но только для подготовки аргументов к дальнейшему сравнению.

ElectricalStorm
Зачем сравнивать пароли по звучанию?

Сложности в сравнении:
Разные регистры символов - решается (обе строки перед сравнением toUpperCase())
В русских словах пишут английские буквы (могут и ноль написать вместо буквы "О") и наоборот - решается (выше описано как)
Путают прямой/обратный слэши, кавычки/апострофы - решается (замена обр. слэшей на прямые, апострофы с кавычками вообще убираются)
Слова разделяют произвольным числом пробелов - решается (замена "\\s+" на " " в терминах regexp)
Ставят пробелы в конце и в начале названия - решается (пробелы в конце и в начале названия убиваются, если есть)
Жестоко сокращают слова (д/инф д/проф-ки п/о) - требует решения...

В принципе как проверить похожи слова или нет обсуждалось недавно в Алгоритмах, думаю запрограммить готовый алгоритм будет не сложно: http://forum.vingrad.ru/index.php?showtopic=31253

Zandar

Есть такой пакет, но он достачно слабенький.
Он ищет простые мэчи , но не более того.
Что запарсить сложный текест - на мой взгляд лучше пользоваться
апачевским регэкспом.

Цитата(Bors @ 27.10.2004, 11:08)

Что запарсить сложный текест - на мой взгляд лучше пользоваться апачевским регэкспом.

Могу только подтвердить - апачевский может больше.

Цитата(AntonSaburov @ 27.10.2004, 12:06)

Цитата(Bors @ 27.10.2004, 11:08) Что запарсить сложный текест - на мой взгляд лучше пользоваться апачевским регэкспом. Могу только подтвердить - апачевский может больше.

На базе регэкспа как-то писал симулятор для WAPa и SMSa.
Так там надо было парсить и URLи и собственно сообщения.
Возможности просто гиганские, если хорошо разбираешься в паттеренах регэкспа...

Короче. MSWord. Печатаем слово с ошибкой. MSWord предлагает список "правильных" слов из которого можно выбрать замену. Вот похожий по смыслу алгоритм мне нужен. Только не для одиночных слов, а для наименований, которые есть выше. Уже есть ключевые наметки как это сделать. Некоторые из них описаны выше. Половина (если не больше) преобразований есс-но на регекспах. Но ими одними не обойтись. Как доделаю выложу для дальнейшего обсуждения.
Добавлено @ 11:17

Цитата(3 @ 27.10.2004, 13:18)

В принципе как проверить похожи слова или нет обсуждалось недавно в Алгоритмах, думаю запрограммить готовый алгоритм будет не сложно: http://forum.vingrad.ru/index.php?showtopic=31253

Мдя то что нада