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

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

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

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

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

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

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

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

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

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

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

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

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

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

(55) Проще сделать готовый сервис, так как программу всё равно как-то нужно будет обучать.

Тут получается так - что сервис - это одна база для всех, а если программа у клиента - то у каждого - своя база.

(56) Я просто с техническими прайсами по электротехнике сталкивался - так там вообще понять, что в нём записано, можно только после того, как увидишь описание - так как сплошные аббревиатуры и сокращения.

(45)  нормально оно выдает
Чем длиннее поисковая фраза тем нечеткий поиск ищет лучше

Потому что если задать поиск
Белая бумага
То туда попадет и
Обои с белой бумагой

А вот когда получил подмножество нечетким поиском его можно уже дополнительно просеивать более формальными методами чем нечеткий поиск

(58)  я делал такую хрень для магазина радиодеталей
Там все радиодетали похожи на все по маркировке
Но даже на этом буквенноцифровом абракадабре нечеткий с последующей эмпирической обработкой давал вполне приемлемые результаты

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

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

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

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

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

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

(63)  не взлетит

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

(65) Вся проблема в том, что у поставщика в прайсе будет указано "SvetoCopy A4" - и все алгоритмы идут в лес.

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

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

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

(70) Просто, первым этапом он должен найти все SvetoCopy, так как это слово "основное", а потом уже по ним выбирать формат.

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

(65)  ээээ дружище.... Ты белую увязываешь с зеленым и красным чтобы разделить, поэтому сначала надо обобщить подмножество чегото чтобы потом по этому подмножиству делить

Если ты ищешь белую бумагу и не привязываешься к грамматике и всякой семантике

То белая линованная мелованная в зеленой пачке с серым оттенком бумага - у тебя выпадет из поиска, так как отфильтруется и по зеленому и по серому с учетом того что слово бумага гораздо ближе к слову зеленая и серая чем к слову белая

И это ты знаешь что к бумаге надо фильтровать по цвету
А что то другое по критерию веса тяжелая легкая
Затрахаешься

Если делать универсально то все равно придешь к тем же самым нечетким поискам

(71) Мыши A4Tech очень обидятся, так как некоторые их пишут A4 Tech

(67)  дай ссылку и пример

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

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

(69) вот именно

(72)  здрасте вам в люлю
Вот есть такая фраза

Daster mhgdas yjkiop dxrtyhret

Какое здесь слово основное?

(75)  пофиг
Пробел на поиск не влияет ибо он не звучит фонетически
Поэтому перед поиском нормализуем все

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

(80) Только A4Tech и A4 Tech - будут разные понятия - никто же не знает, что можно склеивать как угодно слова.

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

(77)  так или иначе видимо придется делать некую кластеризацию
То есть сначала определить для вашей конторы базовые кластеры
И далее както считать признаки, у которых расстояние до кластера минимальные

Для кластера бумага весомыми будут признаки цветов
Для кластера школьных ранцев весомыми будут признаки материала
И так далее

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

(85) Он должен найти основное слово "мышь" - точнее - оно должно быть задано заранее.

(83)  да пофиг точно также будут выкидываться всякие # % N
Все в итоге сведется к этому самому расстоянию ливенгука или как там его...

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

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

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

(86)  и как оно будет задано заранее?
Все равно приходишь к некоторым формальным требованиям если необходимо усилить качество
Типа того что главное слово то есть предмет поиска должно стоять первым

Тогда
Мышь серая
И
Серая мышь

При поиске будут давать принципиально разные результаты
Ибо во втором случае
На серую мышь больше похожа серая бумага чем черная мышь

(87) Ну, не всегда это хорошо, так как Хлопок 40% выглядит куда лучше чем без процента.

(91) Нужно знать значения всех слов - просто компьютер не всегда глагол от существительного отличит (например "печь")

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

(90)  ответь на (79)

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

(95) Там у тебя одни артикулы - а они или повторяются точно также или вообще нигде больше не встречаются.

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

(95) >Daster mhgdas yjkiop dxrtyhret

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

(94)  фиг тебе
Нечеткий сработает лучше

есть список
Мышь серая
Серая бумага

Ищем
Серый мыщь

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

(98) Для простых формальных или искусственных языков без неопределенностей эта задача уже решена.
Сча пытают на естественных языках для перевода между языками.

А что делать, когда описывается комплект - например - "mini-компьютер EEPC клавиатура мышь в комплекте".

(99)  юзер у тебя затрахается говорить какое слово основное, и какие к нему признаки подходят
Потому сто для разных областей одно и то же слово может быть основным и неосновным

(100) А вот и нифига )) потому что
блабла Мышь ляля серая бумбум
блабла Серая бумбум бумага ляля

и ищем Серый мыщь )) - ибо по расстояние Левенштайна меньше ибо меньшее число перестановок/вставок

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

Цель перенести задачу "обучения" с прога на юзера.

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

(104)  а вот и фига, потому что в тоем этом приере мышь и бумага не являются главными для нечеткого поиска эти две фразы означают почти одно и тоже потому что блабла бумбум ляля, а то что жто мышь или бумага - несущественно

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

Это мгновенно будет! Никаких десятков секунд (или минут) на нечеткий поиск для одной фразы.

(108)+ Причем комп уже будет знать что если ищем "мышь" то "бумагу" искать не нуна.
Пользователь ему это неявно между делом объяснил когда первоначально данные разносил.
Ведь "мышь" и "бумага" ни в одном примере вместе никогда не встретились...

(105)  ага я подлерживаю, но малоэффективно
Ибо юзеры и самито не особо способны учиться а уж учить

Не проще ли
Автоматом гоним нечеткое сравнение прайсов с нашей базой
Запомнили высокие совпадения
Далее подсовываем юзверю высокие совпадения по убыванию - он либо подтверждает либо отвергает
Подтверждения ставим в привязку

Отвергнутые прогоняем снова по базе за исключением сделанных привязок, снова подтверждаем или отвергаем
Возможен также вариант что позицию из прайса отмечаем как ненужную

Тяжело первый прайс делать

Далее каждый последующий прайс прогоняем не только по нашей базе но и по уже сделанным привязкам

Менеджеры снова подтверждают или отвергают

С каждым последующим прайсом автопривязки будут все более релевантными.

Когда у поставщика меняется прайс он не меняется кардинально, ушла бумага кнауф появилась бумага Белла, а с учетом что коротких наименований я думаю всетаки мало прогон через автопривязку снрва сработает

Если такие прогоны делать часто - будет автоопределение новинок, автоопределение мусора

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

Если контора занимается ВСЕМ - то булет проблематично, потому что это огромная КУЧА - а ничего лучше поисковых машин пока не придумали

(108)  понимаешь в чем проблема
Менеджер будет искать в первую очередь мышь, а потом окажется что усб не подходит
А сисадмину определяющим словом будет не просто "мышь" а "мышь усб"

(109)  а если в товаре мышь встретится слово бкмага как поясняющее - такая мышь отвалится из поиска ибо бумага, но в жтом контексте бумага не является значимым, а комто это как поймет?

(109)  по сути ты все равно определяешь некие "слова"
Которые должны обязательно встретиться в поиске
Но стоит чуть криво будет и как оно тогла?

Ну вот определил ты что к мышам относится все что имеет в себе
Слова рядом или нерядом "мышь" и "бордовая"
А в прайсе будет
Устройство позиционирования куросра бордовое
Или мщь брдвая

И что?

(112) Ну у меня задачка немного проще/иная.
Взять эту гору разных кривых наименований и создать на их основе некий специализированный каталог с набором справочников для описания объектов.

И этот справочник с привязками к кривым наименованиям разных поставщиков выдавать в пользование.

Если был бы такой алгоритм, который бы стопудово соотносил фразы одна с другой - на таком сервисе можно было бы поднять миллиарды

Но я такого сервиса не видел

(113) Это будет указывать пользователь в случае не верного сопоставление слов - справочникам.
Моя задача облегчить по максимуму это сопоставление.


(115) Думаешь я откажусь от лярдов? ))

У меня как бы в (0) маленькая подзадачка огромной целой задачищи

(114)  не взлетит
Ибо прайсы поставщиков постоянно дышат
Тебе придется чтобы пользователь постоянно сидел и учил систему
Та же самая задача что я описал со своей схемой работы по нечеткому поиску
Но проблема в том, что ты больше опираешься на мнение пользователя - а это люди они устают, им надоедает и тд

(118) Вот вот, прекрасно это понимаю и хочу по максимум убрать с пользователей задачу тыкать.
Оставить только задачу смотреть/проверять глазками правильно ли работает система и тыкать только когда "не правильно".

(119)+ А система чтобы сама обучалась...

могу быть неправ
По существу темы

Но если сделаешь такой инструментарий - дай попробовать. У мння есть лавочник с чехлами аксессуарами для телефонов

Можно будет на нем погонять

Я на нем гонял привязки по нечеткому поиску - в подавляющем колве случаев привязка в полуавтоматическом режиме работала на ура. Для позиции из прайса наша нужная позиция практически всегда нахожилась на первом экране похожих позиций в первой пятерке

(120)+ И да самая суть что за счет лени пользователей лишний раз тыкнуть будет минимизация ошибок кривого распознавания.

Потому что один не тыкнул, так другой тыкнет и сделает правильно что пропустил 1-й. А вот оба они меньше раз тыкнут не туда куда нуна.

(119)  подмена понятий
Так как тыкать глазками придется НА ВСЕ - чтобы найти неправильное
В итоге задача сводится к моей схеме работы
Делаешь первоначальные привязки
Дальше ставишь порог
Дальше при появлении непривязанных позиций
Все что выше порога - очень высокая вероятность что автопривязка сработала правильно - это сверяется очень быстро
Низкие значения автопривязки - это либо забиваешь болт либо проверяешь в посл. Очередь

Кста сча гугл вовсю это юзает за счет обучения с помощью своего браузера Хрома.

Фишка что пользователь ищет что то по ключевым словам а затем отслеживаются переходы на сайты из поисковой выдачи и сколько времени там провел пользователь который искал.

Если выдали не то то пользователь почти сразу закрывает сайт и гугл его минусует для слов запроса. А если долго на сайте просидел то плюсует для слов. И самое веселое что он это настраивает индивидуально для юзеров ))

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

(123) Хочу максимально исключить понятие "порог".

(122)  то что пропустил первый это как раз не проблема
А вот если первый тыкнул неправильно - а ведь онто как раз рисует правила путем тыканья - у тебя случится попа

(125)  не выйдет
В том или ином виде он будет имхо

Если в качестве поиска я топчу
Бумага - я что ищу? Любую бумагу
А если я втопчу
Бумага зеленая - значит ли это что мне не надо выдавать бумагу салатовую?

(126) Угу, особенно если 2-й это не заметит (или 1-й сам) и не исправит.

Есть такая проблема у нейронных сетей и прочих алгоритмов машинного обучения как "переобучение".

(127) >Бумага зеленая - значит ли это что мне не надо выдавать бумагу салатовую?

Если при первоначальном обучении когда разбирали признаки сказали что "зеленая"<>"салатовая" то да не покажет и исключит.
Но оно при обучении (или 1-й раз встретилась) про салатовую спросит и если занесут как синоним к зеленой то все ок будет и даже супер.

Имхо все равно не туда пошли

Загони свои прайсы тупо на какойнить свой сайт-классификатор
И для поиска соответствия используй поисковую машину яндекса, ограничив ее область поиска этим своим сайтом

И все

(129) Можно заставить юзера печатать заново слова, а не просто добавлять тыком как новое.

Т.е. сначала предложит выбрать синоним и если нету синонима то уже заносим как новый признак.

Но тут еще думать и думать.

(129)  затрахаетесь
Придется обучать или исключать комбинации всех со всеми
Потому что
Бумагу зеленую и бумагу салатовую следует считать равными
А бумагу зеленую с бумагой салатовой с красноватым оттенком следует не считать одинаковыми

(130) Гениальная идея особенно если заставить яндекс/гугл через апи еще и этот сайт "доклассифицировать" ))

(132) Игру кит или кот знаем? Ну или http://ru.akinator.com/

(131)  я над аналогичной задачей уже гдето с год вяло думаю
У меня лавочник хочет свой товары описывать произвольным набором характеристик с произвольными значениями жтих характеристик и чтобы при жтом при поиске вот клиент хочет чегото такого - чтобы выдавалось именно то что клиенту надо

(133)  не понял какой смысл ты вложил в слово доклассифицировать?

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

(134)+ Кста попробовать загадать если Злопчинский то интересно угадает?

(134)  хрен там
Загадал гендальфа из властелина колец
И нихрена не отгадали
Так как на впрос
Играл ли персонаж во властелине колец мой ответ нет
Гендальф не играл во властелине колец
Ибо это не фильм

(136) Сопоставить неклассифицированный хлам к уже классифицированным четким детально расписанным позициям.

(138) У них база переобучена)) Гендальф был во Властелине Колец )))

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

(140)  гендальф в фильме - не был
Фильм был про гендальфа
Разн цу чувствуешь?
Это как про бумагу, которая не главная

(142) Угу, но главное чтобы это чувствовали юзеры ))

Понятно что даже простое нечеткое сопоставление можно легко криво напривязывать, но да это сложнее сделать чем с таким продвинутым как хочу я.

Но это продвинутое для умного/грамотного но ленивого пользователя ))

(143)+ В смысле когда обучение идет, пользоваться готовыми то уже кто угодно сможет.
Кста если сохранять привязки юзеров и высчитывать % правильности причем делать дубляж для одного и того же.

То будет интересная система самомодерирования и самоисправления для базы. Когда неправильная оценка плохого юзера будет перебиваться хорошими оценками хороших юзеров ))

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

(145) Чтобы сделать сайт все равно нужен некий алгоритм чтоб операторы могли быстро и удобно создавать/править/привязывать номенклатуру.
И да типовой каталог (онлайн) публичный пусть будет а монетизация на привязках (к другим каталогам) и api.

(0) гугл целый глобальный бизнес на таком алгоритме построил, а ты хочешь им какие-то сцаные наименования формировать. Узко мыслишь :)

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

(148) Каким образом если не секрет?

Если в виде реализации вместо
"private static String longestCS(String a, String b)"
будет
"private static String longestCS(ArrayList<String> a)"
то просто замечательно бы...

(149)+ Все не надо, сам дотумкал, можно же матрицу многомерную (по числу строк) делать.

(144) да, что-то похожее у меня было