Как реализовать умное сравнение строк?

Question

[Turtle_Onni]

Всем привет!

Возникла проблема со сравнением строк.
Задача: Из одной таблицы(она огромна) необходимо сравнить наименование из другой таблицы(тоже огромна, более 20 тысяч строк). Пример наименование1.таблица1 = "Автоматический выключатель KDJF39484", наименование2.таблица2 = "Выключатель автоматический KDJF39484". Или "гайка СБВ-4В ГОСТ.83" и "Гайка СБВ-4ВГОСТ.83". Могут быть разные разделители и присуствие или отсутствие пробелов.
Каким образом сравнить эти строки чтобы выявить что это одно и тоже название?

Буду признательна ссылкам и литературе, вашим советам.

Comments

[Anton]

не совсем ясно, вы будете сравнивать строки в самой СУБД или посредством приложения, которое будет посылать запрос в СУБД?

[Turtle_Onni]

Буду работать через приложение.

[d'Ivan]

Turtle_Onni: А можно ли дополнить список какие трансформации над текстом приводят к дубликатам?
1. увеличение количества пробелов между словами.
2. перемена мест любых слов
3. использование разделителей (каких? где относительно слов?)
4. замена заглавных/строчных букв в словах

Ещё, может быть, каталоговый номер ("KDJF39484") стоит отделить в отдельное поле.

[d'Ivan]

Turtle_Onni: по теме al_gon уже отвечал в Как реализовать поиск схожести двух строк (названия продуктов)?

[АртемЪ]

Опечатки в номере возможны? Или замена схожих букв из разных алфавитов?

[al_gon]

АртемЪ: Не знаю как у Turtle_Onni . На практике это сплош и рядом.

[Turtle_Onni]

АртемЪ: Да, в этом и проблема. Каждый человек записывает в разном порядке название позиции. Ориентированть на маркировку нельзя, иногда бывает вообще обычное название "Винт", и тут приходится выбирать из всех схожих вариантов в ручную. Метод Левенштейна не подходит.

Answer 1

[Артем Воронов]

Можно начать с расстояния Левенштейна.

Comments

[Владимир]

https://postgrespro.ru/docs/postgrespro/9.5/fuzzys...

[azShoo]

С расстоянием Левенштейна всё не так однозначно, т.к. добавление пробела (LGG3 vs LG G3) и замена одного символа (LG G3 vs LG G4) даст одинаковое расстояние, но при этом ожидаемый результат разный.
Т.е. как минимум придется сначала выпилить все возможные разделители из обоих строк.

[d'Ivan]

Безсмысленно, ибо "Выключатель автоматический" и "Автоматический выключатель" выдаст на сравнении большое расстояние.

Answer 2

[Schullz]

Без внятного ТЗ результат ХЗ

Comments

[Turtle_Onni]

Что не понятно?

Answer 3

[Alex]

LCASE( REPLACE ( REPLACE ( REPLACE ( REPLACE ( )))) = LCASE( REPLACE ( REPLACE ( REPLACE ( REPLACE ( ))))

Comments

[Alex]

Если только разделители, а вот порядок слов, сложнее, тогда уж проще отрезать не значимые слова, только до кода СБВ-4В ГОСТ.83 или KDJF39484

Answer 4

[Дмитрий Дарт]

На PHP есть, но на C# самим придётся перекладывать:

function GetUniqueStrings($a=array()){

	if(is_array($a)) {
		$out = array();
		foreach($a as $k=>$str){

             	$str = strip_tags(htmlspecialchars(trim($str)));
            	$str = str_replace('  ', ' ', $str);
            	$str = mb_strtolower($str, mb_detect_encoding($str));//не учитываем регистр

			$arr = explode(' ', $str);
	
			$out[$k] = array_reduce($arr, function($sum, $cur){
				$sum += sprintf("%u", crc32($cur));
				return $sum;
			});
		}
		return array_intersect_key($a, array_unique($out));
	}
}
 

$MyArray = [
'автоматический выключатель KDJF39484',
'выключатель автоматический KDJF39484',
'KDJF39484 автоматический выключатель'
];

print_r(GetUniqueStrings($MyArray));

Дефисы можно заменить на пробелы. В случае опечаток типа 4ВГОСТ действительно что-то типа Левенштейна нужно.

Answer 5

[xmoonlight]

Нечёткое сравнение строк (включая опечатки, фонетику и прочее): здесь.
Также, на странице можно тестировать на своих данных.

Answer 6

[al_gon]

По большим данным только с поисковым движком.
Всё остальное это сравнения 1:1. Это не промышленные масштабы.

Как реализовать поиск схожести двух строк (названия продуктов)?

Answer 7

[d'Ivan]

Мне пришёл в голову следующий примитивный алгоритм:

1. предобработка: переводим в строке заглавные символы в строчные ("Гайка" -> "гайка")
   
2. разбиваем строку на токены/слова, разделяемые любым количеством пробелов ("ббб ааа ввв" -> ["ббб", "ааа", "ввв"])
   
3. полученный массив слов сортируем лексикографически (["ааа", "ббб", "ввв"])
   
4. для последующего сравнения соединим обратно в строку (["ааа", "ббб", "ввв"] -> "ааа ббб ввв")
   
5. полученные "нормализованные" строки сравниваем при помощи расстояния Левенштейна
   

Согласно этому алгоритму из строк "Автоматический выключатель KDJF39484" и "Выключатель автоматический KDJF39484" на выходе получится одинаковая строка "kdjf39484 автоматический выключатель".
Таким образом, расстояние Левенштейна между ними будет равно нулю.

Для строк "гайка СБВ-4В ГОСТ.83", "Гайка СБВ-4ВГОСТ.83" результат хуже ожидаемого из-за того что отсортированы слова "СБВ-4В ГОСТ.83" как "гост.83 сбв-4в". Так получилось из-за того что слитно были написаны каталоговый номер и название стандарта.
Для решения данной проблемы я бы получил из БД репрезентативную выборку всех возможных вариантов наименований, в которых фигурирует "ГОСТ" (без разницы заглавными или строчными) и тогда составил бы правила для отделения от других слов через пробел при помощи регулярных выражений или другими способами. Аналогично в случае с другими названиями стандартов (ISO, ...).

Пример на языке Ruby:
https://gist.github.com/romiras/386e3694a59949f6be...

simple_fuzzy_match(
  ' Автоматический выключатель KDJF39484  ',
  'Выключатель автоматический  KDJF39484'
)

выдаёт разницу 0 для "нормализованных" строк, следовательно, они идентичны.

Comments

[d-stream]

"KDJF39484 Автаматический выключатель" и "Афтомат KDJF39484" дадут огромную разницу, хотя партнамбер у них идентичен.

Но тут уже проблема архитектуры в которой код (уникальный или близкий к уникальному) почему-то живет вместе с названиями, описаниями и примечаниями.

Можно слегка "покостылять" и вычищать из сравнения коды элементов, точнее вычленять их (например сверяясь с каталогом) и для позиций с существующим и совпадающим кодом - давать "точное совпадение" независимо от остального текста.

Ну и тюнинг дальше - структура партномеров, т.к. зачастую код может состоять из уникального идентификатора + паразитных кодов (типа цвета, страны и т.п.)

Как образчики:
HP Microserver - 722320-B21 где B21 - собственно РФ
Гиперлайновский шкаф: TSA-3261-GD-RAL9004 - это черный по RAL (RAL9004), со стеклянной (GD) дверью шириной 600, глубиной 1000 мм и высотой 32юнита
соответственно для гиперлайна приоритеты сравнения должны были бы идти как TSA(серия) -> XXYZ(размеры) -> QQ (тип двери) -> RALcccc (цвет)

Answer 8

[igruschkafox]

Все выше написавшие без образования :)
Сорри ребята :)

Если мы говорим про MS SQL
то в Integration Services имеется Fussy Group и Fussy LookUP

Там сравнение идет по 7 алгоритмам (расстояние между буквами, сколько символов надо заменить, расстояние между символами на клавиатуре и тд)

Вот видео для тех кому лень гуглить
https://www.techdays.ru/videos/1378.html

в оракле тоже такое есть (по моему называется Дата директор)

Comments

[al_gon]

Я думаю никто необиделся, вам же надо как-то привлечь к себе внимание. Тем более с MS SQL

[al_gon]

igruschkafox:
Видео как вводный материал интересно даже, если нет возмножности или желания использовать MS SQL.
Спасибо.

Но вопрос в другом, почему фирмы партнёры Microsoft полностью "обвещеные" технологиями и экспертами по ним в том числе по MS SQL ищут решения на стороне?
Это не мое словоблюдие с бодуна, это рыночные реалии.

[al_gon]

Я к тому,что одна технология или один подход не могут быть панацеей в вопросе "нечёткого" поиска.

[igruschkafox]

al_gon: Есть вопрос - как реализовать "Умное сравнение" ?
и есть уже встроенный механизм от майкрософт

Неужели надо изобретать велосипед ?
К тому же я упомянул - что есть и другие готовые решения помимо майкрософту (например у Оракле несколько таких утилит)

И все самодельные алгоритмы на голову проигрывают решениям от крупных корпораций - это объективная реальность в которой мы живем