Быстрый алгоритм наибольших общих подстрок

Требуется среди множества строк найти наибольшие общие подстроки с начала/конца строк.

Задачка осложняется что некоторые строки могут не содержать требуемых общих подстрок и требуется разделение всех строк на некие "группы" для которых существуют требуемые общие подстроки.

Типовой алгоритм https://ru.wikipedia.org/wiki/Наибольшая_общая_подстрока слишком медленно работает, т.к. сравнивает строки только попарно.

И когда исходных строк от сотен до десятков тысяч получаем полный затык.

Пример:
Товар1 арт1 зеленый
Товар2 арт2 красный
Товар3 арт3 синий
Товар1 арт4 серый

Ищем общие подстроки "справа" для: ("Товар1 ", "Товар2 ", "Товар3 ", "Товарр1 ")
Находим: "р1 " - 2 совпадения и " " - 4 совпадения

И общие подстроки "слева" для: (" зеленый", " красный", "синий", " серый")
Находим: " " - 4 совпадения и " с" - 2 совпадения

Зачем это нужно? А чтобы разделять длинные одностроковые (наименования) на составляющие построки для выделения характеристик.
Вывод: вероятнее всего " " и " " являются "разделителями" характеристик. Теоретически разделителями может быть что угодно - ";", "," "(", ")" и "символ табуляции" и т.д.

(1) Угу для заведения номенклатуры "по правилам" и сопоставления автоматического.
Простое деление на слова по " " (пробелу) не катит, потому что любят такое делать:

"Товар1 арт. 45454 (4545454;валвла-алвалв,ава23) - оуаова"

(2)+ Думал задать список/справочник "ключевых слов" (часто встречающиеся служебные слова или характеристики типовые).
Искать их в наименованиях и то что слева/справа от ключевых делать разделителями.

(5) Да так и есть в правильной базе оно все так, у товаров есть только наборы реквизитов/свойств из готовых справочников.

Но чтобы сделать загрузку авто в эту правильную базу для сравнения из кривых "прайсов" требуется решить эту задачку.

И все осложняется тем что каких то одинаковых артикулов по факту нету (( Уникальный артикул/ШК производителя/поставщика это то что не распозналось "по справочникам".

(4) Вот это и хочу сделать как результат, но что поделать если данные исходные только в таком виде доступные есть?

Чтобы было понятнее зачем то банально заходим на Али или другие подобные "барахолки" типа Авито и видим полный изврат.
Когда чтобы нормально найти что то приходится извращаться с разными наборами ключевых слов. Потому что продаваны сволочи и слово "телефон"/"phone" к примеру засовывают во все подряд ((

(7) Угу вот и хочу по "набору свойств" классифицировать, чтобы потом натравить туда ИНС и получить какой то результат.

Пример 1-й место (у меня) с али по поиску "телефон"/"phone" это
Wireless IP Camera WiFi Micro SD Network 2 Ways Audio Security Camera Family Video Surveillance HD CCTV Support Smart Phone View

Человек понимает что это "беспроводная камера с поддержкой просмотра на телефоне" - как объяснить это компьютеру?

А потом продать эту AI хрень самому али... ))

(10)+ Пример с разделителями "/" или " ":

"3.5mm Audio Plug Wired Mini Microphone Portable Stereo Condenser Mic for Chatting/Karaoke/PC/Phone/Ipad etc with Lavalier Clip"

(13) Верно! Но сначала надо "разделить" это на составляющие "подстроки-слова".
Потом по "набору слов рядом" можно уже распознавать "фразы".

(14)+ К примеру вместо фразы "Support Smart Phone View" может быть фраза-аналог "Support View on/with Smart Phone"

(16) Еще более не решаемая задачка (( Все типовые распознавалки изначально предполагают задачу разделения на слова уже решенной.

Ибо если искать все "ключевые слова" в тексте это просто нереальная задача.

Кстати пример с "али" это просто самый наглядно-фиговый. Реально нужно для некоторых крупных аггрегаторов-поставщиков типа Мерлиона и еще по канцелярке клиент готов заплатить для разных файликов/тетрадочек.

Вот как оно у мерлиона выглядит http://merlion.com/catalog/list/1333/

(19)+ В смысле мой мелкие клиентики просят им "нечто придумать", а то счас менагеры на заказах зашиваются при поиске по каталогам разным.

(19)+ Сорри пример не совсем правильный, с техникой оно попроще (хотя расходка это пипец) а вот такое http://merlion.com/catalog/list/1186/,
где "Скрепки Alco 458-26 пластиковая оболочка домик 26мм ассорти (упак.:500шт) пластиковая коробка".

И в системе которая доступ по API оно только в таком виде и все.

(22) Да согласен, но не мерлионом единым ))
Хочется то изобрести и реализовать некий единый универсальный алгоритм/сервис.
И чтобы можно было его гибко настраивать и на что угодно натравливать.

(24) Отличная штука, но на изучение слишком много времени уходит (( Простых юзверей этому трюку не обучить.

В отличие от: Возьмите несколько примеров и разберите их вручную, попробуйте как оно само разбирает прочие наименования. Повторяйте до требуемого результата на не правильно разобранных.

(25)+ Сейчас уже сваяна некая альфа-версия этого дела но она дико тормозная и приходится сначала пользователю указывать вручную "разделители" на примерах.
И оно зараза не верно часто делит когда "-" или "/" это не разделитель а внутри сущности/признака.

(27) Ага вот где бы кластер/суперкомп только добыть? Уже и вычислениями/субд на GPU даже озадачился от отчаяние что алгоритму не придумать.

(29) Угу хотел то чтобы пользователь указывал только "варианты", которые заносятся в справочники нужные.
Затем простая разбивка на слова и поиск слов в справочниках на полное соответствие без "like".
Далее банально битовый хеш по признакам-словам в наименованиях и вот они вместе родимые и шустро.

(30) Слишком медленно полный поиск, реально не выходит применять.

Если обычный полнотекстовый индекс для всех "прайсов" то он строится медленнее чем прайсы обновляются ))

(33) А вот это банально, юзеры при указании "признаков" могут занести в справочник как новый или как синоним.

(38) Ближе к натоптал фразу и она ищется в нескольких огромных списках.
Обычная задача для менагера найти у кого (из поставщиков) есть данный товар (требуемый клиенту или для пополнения на склад).
Причем предполагается что товары еще с нашим товаром не сопоставлены каким то образом.

Задачка в лоб через нечеткое сравнение строк решается отвратительно и очень долго.
Метод N-грамм и прочие которые применяют крупные поисковики (гугл, яндекс и т.д.) очень хороши но требуется исключение не нужных результатов.

Ищет менагер бумагу белую, та ему не нужно не белую а цветную показывать, причем он не говорит/перечисляет все ненужные слова (цветная, зеленая)

(39)+ И вот чтобы эту задачку решить нуна научиться быстро разделять "наименования" на "слова". Причем когда они разделяются не простыми " " (пробелами) а разными "-", "/" и прочими скобками и другими символами или даже несколькими символами.

К примеру " арт. " это бесполезная штук и просто разделитель.

(40) Дико много и проблема когда реальные каталоги номенклатуры то там уже минуты на ответ, менагер помрет ждать.
И нечеткое оно слишком нечетко результат выдает, нужна точность почти как человек может.

(44) Дык согласен что это "разделитель" или ключевой указатель для "признака" рядом.

(46) Да можно делать с предварительной обработкой но размеры индексов полнотекстовых такие дикие выходят что простого диска легко не хватит.

(48) Согласен но это уже целая служба и штаты сотрудников. Хочу их заменить умным софтом.

К примеру когда то нужен был переводчик чтобы понять текст на китайском... сча можно просто Хром поставить.

(52)+ * человеческий переводчик с зарплатой

(51) Но от идеи программы на компе клиента придется тогда отказаться, это уже целый тормозной комплекс для крупняка и он у них уже есть. И делать только сервис с дорогой поддержкой/обслуживанием.

(54) Верно! Но чтобы правильно искать сначала нужно решить задачку (0) - "разделить на слова".

(58) Угу аббревиатуры и сокращения они везде. Но поднятие подобного сервиса уже не потяну никак.
Попробовал и тупо времени не хватает на все задачки не выходит расклонироваться.

(59) Чтобы просеивать формальными методами один фиг нужно разделить. И фишка что я то хотел получить ускорение за счет предварительного разделения.

А не после того как ждали полминуты-минуту на поиск и потом еще ждем когда прочие методы отработают.

Смысл что искать нечетким поиском похожие длинные фразы хуже, чем тем же нечетким или даже четким по синонимом найти 10 слов.
И по % совпадений слов, причем с исключением лишних слов (когда ищем белую, автоматом выкидыватся из поиска/подбора цветная|зеленая|красная), шустро подбираем что нуна.

(66) Уже давно взлетело, попробуй поиск в 2гис ))

(67)+ Но у них четкая отрасль/ограничение: только объекты/здания/фирмы на карте.

(68) Если ищем А4 то автоматом уже не найдутся "SvetoCopy A3" так что не совсем в лес.
А простой нечеткий выдаст все с "SvetoCopy АX".

(70)+ т.е. при справочники они имеют признак альтернативности и если указан "А4" то все прочие из этого справочника размера из результата исключаются автоматом.

(71)+ А справочник "марок" типа "SvetoCopy" это аналоги для просто "бумага".

(74) Немного не так но да )) суть алгоритма более хитрая в последущем. Оно делит все сущности/объекты/конретную номенклатуру на некие "классы" для которых задаются допустимые сочетания признаков.
Получается весьма сложная структура которая затем используется для подбора/поиска.

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

(80) да это https://ru.wikipedia.org/wiki/Soundex

(82) Вот и мне некогда и не хочется предусматривать все варианты кривого написания. Хочу чтобы юзеры сами сказали что "A4Tech"="A4 Tech" и что " " тут не разделитель а часть "слова".

(83)+ Т.е. "Мышь A4 Tech Серая USB" разделитель будут "ь " и " С"

(85)+ Ну или разделители "ь A" и "h С" но что части этих "разделителей" включатся в "признаки" слева и справа по нужному числу символов.
Разделитель имеет (длину, значение, символы признака слева, символы признака справа)

(88)+ (3,"ь A",1,1) и (3,"h С",1,1)

(86) Хотел чтобы это слово "Мышь" прога подсказала юзеру, а он уже только сказал в какой это справочник засунуть или даже правильно засунули к "Клавиатура" или нет?

>На серую мышь больше похожа серая бумага чем черная мышь
вот именно и простой нечеткий поиск тут врет дико, в отличие от сопоставления по отдельным словам

(93) У нас алфавит и словарь ограничены ))

(95) >Daster mhgdas yjkiop dxrtyhret

для системы не важно какое слово основное )) оно сделает основным то слово которое скажет юзер к примеру "mhgdas" и автоматически получит еще 3 слова "Daster", "yjkiop" и "dxrtyhret" по которым и будет работать.