Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Java: Общие вопросы > Чем сравнивать строки?


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

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

Хочется иметь какую-нить функцию со смыслом:
Код
public float correl (String s1, String s2)

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

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

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

Автор: Zandr 22.10.2004, 07:20
Названия такого рода/состава (и в каталоге и в прайс-листах):
Цитата
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А-Я]+");
- считаем попарно степень схожести кусочков эталонного названия с кусочками прайсового
- считаем суммарную "схожесть", нормируем.

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

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

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

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

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

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

Автор: Светлая 26.10.2004, 19:20
AntonSaburov
Привет, мне тоже очень приятно к вам заглянуть.

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

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

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

Автор: ElectricalStorm 26.10.2004, 23:04
Цитата

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


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

вот прример который сравниват пароли по их звучанию
(правда на 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;
   }
}

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

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

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

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

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

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

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

Автор: Bors 27.10.2004, 10:08
Zandar

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

Автор: AntonSaburov 27.10.2004, 12:06
Цитата(Bors @ 27.10.2004, 11:08)

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

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

Автор: Bors 27.10.2004, 12:26
Цитата(AntonSaburov @ 27.10.2004, 12:06)
Цитата(Bors @ 27.10.2004, 11:08)

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

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

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

Автор: Zandr 2.11.2004, 11:13
Короче. MSWord. Печатаем слово с ошибкой. MSWord предлагает список "правильных" слов из которого можно выбрать замену. Вот похожий по смыслу алгоритм мне нужен. Только не для одиночных слов, а для наименований, которые есть выше. Уже есть ключевые наметки как это сделать. Некоторые из них описаны выше. Половина (если не больше) преобразований есс-но на регекспах. Но ими одними не обойтись. Как доделаю выложу для дальнейшего обсуждения.
Добавлено @ 11:17
Цитата(3 @ 27.10.2004, 13:18)
В принципе как проверить похожи слова или нет обсуждалось недавно в Алгоритмах, думаю запрограммить готовый алгоритм будет не сложно: http://forum.vingrad.ru/index.php?showtopic=31253

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)