Вход | Регистрация

  1  2
Информационные технологии :: Математика и алгоритмы

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

Быстрый алгоритм наибольших общих подстрок
Я
   Garykom
 
22.09.16 - 00:00
Требуется среди множества строк найти наибольшие общие подстроки с начала/конца строк.

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

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

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

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

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

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

Зачем это нужно? А чтобы разделять длинные одностроковые (наименования) на составляющие построки для выделения характеристик.
Вывод: вероятнее всего " " и " " являются "разделителями" характеристик. Теоретически разделителями может быть что угодно - ";", "," "(", ")" и "символ табуляции" и т.д.
 
 
   Garykom
 
101 - 22.09.16 - 02:36
(98) Для простых формальных или искусственных языков без неопределенностей эта задача уже решена.
Сча пытают на естественных языках для перевода между языками.
   Torquader
 
102 - 22.09.16 - 02:36
А что делать, когда описывается комплект - например - "mini-компьютер EEPC клавиатура мышь в комплекте".
   Злопчинский
 
103 - 22.09.16 - 02:37
(99)  юзер у тебя затрахается говорить какое слово основное, и какие к нему признаки подходят
Потому сто для разных областей одно и то же слово может быть основным и неосновным
   Garykom
 
104 - 22.09.16 - 02:38
(100) А вот и нифига )) потому что
блабла Мышь ляля серая бумбум
блабла Серая бумбум бумага ляля

и ищем Серый мыщь )) - ибо по расстояние Левенштайна меньше ибо меньшее число перестановок/вставок
   Garykom
 
105 - 22.09.16 - 02:39
(103) Это уже проблемы пользователя )) фишка что хорошо обученная база в дальнейшем в пользователе не нуждается.

Цель перенести задачу "обучения" с прога на юзера.
   Злопчинский
 
106 - 22.09.16 - 02:39
(101)  прорыва сейчас гугл достиг за счет того что он смотрит в каком окружающем статистическом контексте встречается переводимая фраза слово и отсюда и тащит - была хорошая статья на жту тему - простые статистические методы без всякой привязки к языку позволили существенно повысить качество перевода
   Злопчинский
 
107 - 22.09.16 - 02:42
(104)  а вот и фига, потому что в тоем этом приере мышь и бумага не являются главными для нечеткого поиска эти две фразы означают почти одно и тоже потому что блабла бумбум ляля, а то что жто мышь или бумага - несущественно
   Garykom
 
108 - 22.09.16 - 02:47
(107) Дык суть что в своем алгоритме хочу выделить слова, найти их в готовых справочниках, понять главные они или нет.
И уже откинув все "блабла", "ляля" и "бумбум" искать только по "мышь" и "серая".

Это мгновенно будет! Никаких десятков секунд (или минут) на нечеткий поиск для одной фразы.
   Garykom
 
109 - 22.09.16 - 02:50
(108)+ Причем комп уже будет знать что если ищем "мышь" то "бумагу" искать не нуна.
Пользователь ему это неявно между делом объяснил когда первоначально данные разносил.
Ведь "мышь" и "бумага" ни в одном примере вместе никогда не встретились...
   Злопчинский
 
110 - 22.09.16 - 02:53
(105)  ага я подлерживаю, но малоэффективно
Ибо юзеры и самито не особо способны учиться а уж учить

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

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

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

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

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

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

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

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

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

Если контора занимается ВСЕМ - то булет проблематично, потому что это огромная КУЧА - а ничего лучше поисковых машин пока не придумали
 
 Рекламное место пустует
   Злопчинский
 
111 - 22.09.16 - 02:55
(108)  понимаешь в чем проблема
Менеджер будет искать в первую очередь мышь, а потом окажется что усб не подходит
А сисадмину определяющим словом будет не просто "мышь" а "мышь усб"
   Злопчинский
 
112 - 22.09.16 - 02:57
(109)  а если в товаре мышь встретится слово бкмага как поясняющее - такая мышь отвалится из поиска ибо бумага, но в жтом контексте бумага не является значимым, а комто это как поймет?
   Злопчинский
 
113 - 22.09.16 - 03:01
(109)  по сути ты все равно определяешь некие "слова"
Которые должны обязательно встретиться в поиске
Но стоит чуть криво будет и как оно тогла?

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

И что?
   Garykom
 
114 - 22.09.16 - 03:02
(112) Ну у меня задачка немного проще/иная.
Взять эту гору разных кривых наименований и создать на их основе некий специализированный каталог с набором справочников для описания объектов.

И этот справочник с привязками к кривым наименованиям разных поставщиков выдавать в пользование.
   Злопчинский
 
115 - 22.09.16 - 03:03
Если был бы такой алгоритм, который бы стопудово соотносил фразы одна с другой - на таком сервисе можно было бы поднять миллиарды

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


(115) Думаешь я откажусь от лярдов? ))
   Garykom
 
117 - 22.09.16 - 03:05
У меня как бы в (0) маленькая подзадачка огромной целой задачищи
   Злопчинский
 
118 - 22.09.16 - 03:06
(114)  не взлетит
Ибо прайсы поставщиков постоянно дышат
Тебе придется чтобы пользователь постоянно сидел и учил систему
Та же самая задача что я описал со своей схемой работы по нечеткому поиску
Но проблема в том, что ты больше опираешься на мнение пользователя - а это люди они устают, им надоедает и тд
   Garykom
 
119 - 22.09.16 - 03:07
(118) Вот вот, прекрасно это понимаю и хочу по максимум убрать с пользователей задачу тыкать.
Оставить только задачу смотреть/проверять глазками правильно ли работает система и тыкать только когда "не правильно".
   Garykom
 
120 - 22.09.16 - 03:08
(119)+ А система чтобы сама обучалась...
   Злопчинский
 
121 - 22.09.16 - 03:09
могу быть неправ
По существу темы

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

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

Я на нем гонял привязки по нечеткому поиску - в подавляющем колве случаев привязка в полуавтоматическом режиме работала на ура. Для позиции из прайса наша нужная позиция практически всегда нахожилась на первом экране похожих позиций в первой пятерке
   Garykom
 
122 - 22.09.16 - 03:10
(120)+ И да самая суть что за счет лени пользователей лишний раз тыкнуть будет минимизация ошибок кривого распознавания.

Потому что один не тыкнул, так другой тыкнет и сделает правильно что пропустил 1-й. А вот оба они меньше раз тыкнут не туда куда нуна.
   Злопчинский
 
123 - 22.09.16 - 03:13
(119)  подмена понятий
Так как тыкать глазками придется НА ВСЕ - чтобы найти неправильное
В итоге задача сводится к моей схеме работы
Делаешь первоначальные привязки
Дальше ставишь порог
Дальше при появлении непривязанных позиций
Все что выше порога - очень высокая вероятность что автопривязка сработала правильно - это сверяется очень быстро
Низкие значения автопривязки - это либо забиваешь болт либо проверяешь в посл. Очередь
   Garykom
 
124 - 22.09.16 - 03:14
Кста сча гугл вовсю это юзает за счет обучения с помощью своего браузера Хрома.

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

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

Т.е. разная выдача по одинаковым слова для разной истории поиска и серфинга...
   Garykom
 
125 - 22.09.16 - 03:15
(123) Хочу максимально исключить понятие "порог".
   Злопчинский
 
126 - 22.09.16 - 03:15
(122)  то что пропустил первый это как раз не проблема
А вот если первый тыкнул неправильно - а ведь онто как раз рисует правила путем тыканья - у тебя случится попа
   Злопчинский
 
127 - 22.09.16 - 03:17
(125)  не выйдет
В том или ином виде он будет имхо

Если в качестве поиска я топчу
Бумага - я что ищу? Любую бумагу
А если я втопчу
Бумага зеленая - значит ли это что мне не надо выдавать бумагу салатовую?
   Garykom
 
128 - 22.09.16 - 03:18
(126) Угу, особенно если 2-й это не заметит (или 1-й сам) и не исправит.

Есть такая проблема у нейронных сетей и прочих алгоритмов машинного обучения как "переобучение".
   Garykom
 
129 - 22.09.16 - 03:20
(127) >Бумага зеленая - значит ли это что мне не надо выдавать бумагу салатовую?

Если при первоначальном обучении когда разбирали признаки сказали что "зеленая"<>"салатовая" то да не покажет и исключит.
Но оно при обучении (или 1-й раз встретилась) про салатовую спросит и если занесут как синоним к зеленой то все ок будет и даже супер.
   Злопчинский
 
130 - 22.09.16 - 03:20
Имхо все равно не туда пошли

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

И все
   Garykom
 
131 - 22.09.16 - 03:22
(129) Можно заставить юзера печатать заново слова, а не просто добавлять тыком как новое.

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

Но тут еще думать и думать.
   Злопчинский
 
132 - 22.09.16 - 03:23
(129)  затрахаетесь
Придется обучать или исключать комбинации всех со всеми
Потому что
Бумагу зеленую и бумагу салатовую следует считать равными
А бумагу зеленую с бумагой салатовой с красноватым оттенком следует не считать одинаковыми
   Garykom
 
133 - 22.09.16 - 03:24
(130) Гениальная идея особенно если заставить яндекс/гугл через апи еще и этот сайт "доклассифицировать" ))
 
 
   Garykom
 
134 - 22.09.16 - 03:26
(132) Игру кит или кот знаем? Ну или http://ru.akinator.com/
   Злопчинский
 
135 - 22.09.16 - 03:26
(131)  я над аналогичной задачей уже гдето с год вяло думаю
У меня лавочник хочет свой товары описывать произвольным набором характеристик с произвольными значениями жтих характеристик и чтобы при жтом при поиске вот клиент хочет чегото такого - чтобы выдавалось именно то что клиенту надо
   Злопчинский
 
136 - 22.09.16 - 03:29
(133)  не понял какой смысл ты вложил в слово доклассифицировать?

Ты пополнил свой сайт новыми позициями спсков - через день или два или неделю робот яндекса это доиндексирует хочешь быстрее - заплати яндексу - он будет тебя хоть каждый час индексировать
   Garykom
 
137 - 22.09.16 - 03:32
(134)+ Кста попробовать загадать если Злопчинский то интересно угадает?
   Злопчинский
 
138 - 22.09.16 - 03:33
(134)  хрен там
Загадал гендальфа из властелина колец
И нихрена не отгадали
Так как на впрос
Играл ли персонаж во властелине колец мой ответ нет
Гендальф не играл во властелине колец
Ибо это не фильм
   Garykom
 
139 - 22.09.16 - 03:33
(136) Сопоставить неклассифицированный хлам к уже классифицированным четким детально расписанным позициям.
   Garykom
 
140 - 22.09.16 - 03:34
(138) У них база переобучена)) Гендальф был во Властелине Колец )))
   Злопчинский
 
141 - 22.09.16 - 03:36
Но если отвечать дальше то вообщем угадал, да и то потому что в тех вопросах где я сомневался я давал более положительные моменты
   Злопчинский
 
142 - 22.09.16 - 03:37
(140)  гендальф в фильме - не был
Фильм был про гендальфа
Разн цу чувствуешь?
Это как про бумагу, которая не главная
   Garykom
 
143 - 22.09.16 - 03:46
(142) Угу, но главное чтобы это чувствовали юзеры ))

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

Но это продвинутое для умного/грамотного но ленивого пользователя ))
   Garykom
 
144 - 22.09.16 - 03:49
(143)+ В смысле когда обучение идет, пользоваться готовыми то уже кто угодно сможет.
Кста если сохранять привязки юзеров и высчитывать % правильности причем делать дубляж для одного и того же.

То будет интересная система самомодерирования и самоисправления для базы. Когда неправильная оценка плохого юзера будет перебиваться хорошими оценками хороших юзеров ))
   Torquader
 
145 - 22.09.16 - 11:03
(144) В общем - проще сделать сайт, где хорошо продуманный классификатор товаров - и предложить и покупателям и продавцам пользоваться этим классификатором - тогда точно взлетит.
   Garykom
 
146 - 22.09.16 - 11:25
(145) Чтобы сделать сайт все равно нужен некий алгоритм чтоб операторы могли быстро и удобно создавать/править/привязывать номенклатуру.
И да типовой каталог (онлайн) публичный пусть будет а монетизация на привязках (к другим каталогам) и api.
   Лефмихалыч
 
147 - 22.09.16 - 11:27
(0) гугл целый глобальный бизнес на таком алгоритме построил, а ты хочешь им какие-то сцаные наименования формировать. Узко мыслишь :)
   Loky9
 
148 - 22.09.16 - 20:50
"Типовой алгоритм https://ru.wikipedia.org/wiki/Наибольшая_общая_подстрока слишком медленно работает, т.к. сравнивает строки только попарно."
Там только примеры для двух строк, а сам алгоритм работает с произвольным их количеством.
   Garykom
 
149 - 22.09.16 - 20:54
(148) Каким образом если не секрет?

Если в виде реализации вместо
"private static String longestCS(String a, String b)"
будет
"private static String longestCS(ArrayList<String> a)"
то просто замечательно бы...
 
 Рекламное место пустует
   Garykom
 
150 - 22.09.16 - 21:01
(149)+ Все не надо, сам дотумкал, можно же матрицу многомерную (по числу строк) делать.
   Злопчинский
 
151 - 22.09.16 - 21:09
(144) да, что-то похожее у меня было
  1  2

Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует