Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / MySQL [игнор отключен] [закрыт для гостей] / Выборка частично совпадающих строк / 20 сообщений из 20, страница 1 из 1
14.06.2014, 00:04:27
    #38669224
CthulhUzzz
CthulhUzzz
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
Доброго времени суток. Появилась довольно не тривиальная задача сравнения строк между собой.

Дано:
БД: MySQL
Поле для поиска содержит строку произвольной длины (TEXT). (от 200 до 2000 символов)
Всего в таблице около 4млн. строк.

Задача:
Выбрать из таблицы строки, где имеется частичные совпадения со строкой (совпадающие символы должны идти подряд, а суммарное количество совпадающих символов должно быть не меньше N)

Для примера:
Исходные данные (Жирным выделены совпадения строк):

N=15

ksdlkfj2k3 FDSJKHfka2fsddasFSDKJ HKfsdfsv3vxcsplkfgjlkhjfg
dklashdklJHKfSFLKHSOsdfsv3vxcsplkfgjlL FKHLSIDFflksmdflkjsLDkfOF UEwjp234682
LKHSOsdfsv3vxcsplkfgjlL FKHLSIDFflksmdflkjsLDkfOFfkJEFNKwefojoiw enfKFJ372

Строка запроса: FKHLSIDFflksmdflkjsLDkfOFfkJEFNKwefojoiwADAKFDSJKHfka2fsddasFSDKJJH32h


В базах данных дилетант, так что будут рассматриваться любые способы рационализации поиска (Вплоть до переезда на другую СУБД)
P.S. Возможно можно решить с помощью Sphinx (решения именно моей задачи не нашел)

Спасибо за внимание!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.06.2014, 00:12:16
    #38669227
ScareCrow
ScareCrow
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
substr
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.06.2014, 00:38:55
    #38669238
CthulhUzzz
CthulhUzzz
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
ScareCrow,

Проблема в том, что я не знаю, какая именно часть из исходной строки совпадет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.06.2014, 06:12:12
    #38669542
javajdbc
javajdbc
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
CthulhUzzz,

Говоря русским народным языком -- вы заколебётесь считать.

4 млн строк, скажем 1020 буковок в среднем.
Внутри каждой (каждой из 4 млн!) такой записи есть 1000
подстрок длиной 20 символов.

Т.е. строку запроса, в которой 1.000 20-буквеных варинтов
надо проверить против 1.000 х 4.000.000.000
20-буквеных вариантов в базе.
Т.е. 1.000 х 1.000 х 4.000.000.000 тобишь 4 квадрилиона проверок.

В мире баз данных любят делать разные индексы.
Например можно каждой (в среднем 1020 размерной) записи
сделать 1000 дочерних записей 20-буквеных отрезков.
получится 4 трилиона записей. Построить индекс
и на каждый 1020 размерный запрос запускать 1000 проверок
по индексу.


Кстати, а почему бы нет? размер дочерней таблицы будет все в 20 раз больше исходника,
индек можно сделать на 5-10 символов, в зависимости от кардиналити данных...
Т.е. рамер системы поднимется на два порядка -- если потянете, то может
и взлетит...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.06.2014, 08:53:54
    #38669552
Cygapb-007
Cygapb-007
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
CthulhUzzz,

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

То есть минимум - это полный скан таблицы.

Чтобы он же был и максимумом - достаточно написать функцию сравнения строк заданной длины (т.е. с параметрами "длина подстроки", "шаблон поиска", "очередная анализируемая строка"), и возвращающи
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.06.2014, 08:57:40
    #38669553
Cygapb-007
Cygapb-007
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
сорь, с планшета улетело раньше времени:)

... и возвращающая либо 1 (подстрока найдена), либо 0.

Тогда запрос тривиален:
Код: sql
1.
select * from myTable t where func(@N, @s, t.str);
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
15.06.2014, 09:02:45
    #38669555
Cygapb-007
Cygapb-007
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
PS. хотя, конечно, скан огромной таблицы недешевое удовольствие...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.06.2014, 13:20:53
    #38670326
alex564657498765453
alex564657498765453
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
тут один реализовавыла(на форуме) свои шейлы, или шейпинги, ....

короче суть в том, что он берёт строку исходную

разбивает её на части, и в таблицу шейлов вставлеёт хеши этих частей...

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

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

Это где такое понадобилось ....чтоб подобные запросы были многоразовые???

цепочка днк, это по сути строка , где каждая буква означает аминокислоту.
и есть сравнения разные цепочек днк(поиск вхождений частей одной в другую)
строиться на математическом алгоритме, забыл название, - поиск похожести строк - задача медленная, но решаемая чем полные переборы быстрее.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.06.2014, 20:25:09
    #38670932
S.G.
S.G.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
Если "не меньше N" трансформировать в "равно N", то:
1. Для начала разбить ту большую строку (длины L) на L-N+1 строчек длины N, сформировать из них таблицу из одной колонки, и проиндексировать ее.
например: из "abgnthr" и N=5 получается "abgnt", "bgnth", "gnthr".
2. Ну и дальше одноразовым проходом по 4милионной таблице, берем одно слово за другим, если его длина больше или равна N, то методом, как и в п.1 делим слово на много N-значных подслов и каждое подслово сравниваем на равенство с табличкой из п.1.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.06.2014, 20:27:09
    #38670934
S.G.
S.G.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
.. а если есть возможность, этот алгоритм и данные впихнуть в какую-нибудь in-memory database, то получится может быть не так уж и медленно ;)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.06.2014, 22:19:18
    #38670998
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
Существуют достаточно эффективные алгоритмы поиска наибольшей общей подстроки. Можно запрограммить, но лучше не пользовательской функцией, а UDF. Впрочем, всё равно может оказаться тяжеловато.

Можно пойти по пути предобработки - т.е. подготовить исходный массив данных для быстрой реализации такого алгоритма. Построение суффиксного дерева для каждой записи - это, наверное, уже перебор, а вот словаризация всех подстрок заданной длины (оптимально - наверное, около 2N/3) для предварительного отбора записей перед прогоном через поиск общей подстроки вполне подойдёт.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.06.2014, 07:45:24
    #38671180
Cygapb-007
Cygapb-007
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
Все вышесказанное, конечно, справедливо - для какого-то одного конкретного значения N.

Но ТС хочет N менять произвольно от запроса к запросу. Размер таблицы с одним (на самом деле с двумя, про базовый ПК забыли, ну да не суть) полем, сформированной для всевозможных значений N, можете оценить? Пусть даже с дополнительным UNIQUE(pk, substr), IGNORE ON DUPLICATE (или реализованным через триггер отсевом дубликатов подстрок, для экономии места).

Впрочем, если таблицу создать удастся, и даже проиндексировать по CRC (точнее, по CRC32() ), - то результат может стоить затраченных усилий.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.06.2014, 08:00:24
    #38671183
Cygapb-007
Cygapb-007
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
AkinaМожно запрограммить, но лучше не пользовательской функцией, а UDF.
Жутко извиняюсь - а что такое UDF?

Для MS SQL, вероятно, имелось бы в виду CLR , а вот в MySQL - о чём это?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.06.2014, 08:36:45
    #38671213
tanglir
tanglir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
Cygapb-007, похожая штука: http://dev.mysql.com/doc/refman/5.6/en/adding-functions.html
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.06.2014, 08:56:27
    #38671234
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
Cygapb-007ТС хочет N менять произвольно от запроса к запросуНо тем не менее это значение укладывается в некоторые вменяемые рамки - в заданных задачных условиях вряд ли оно будет равно двум-трём, и тысяче тоже вряд ли...
Рекомендации было бы вырабатывать легче, если бы ТС сфорумлировал хотя бы приблизительно, за каким фаллосом ему всё это нужно, какова предметная область и физика процесса, и что ему нужно делать с полученным результатом, а также какими ресурсами он согласен жертвовать для решения задачи.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
24.06.2014, 18:05:13
    #38678884
CthulhUzzz
CthulhUzzz
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
Akina,

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

Логичным вопросом будет, почему я не хочу пользоваться традиционным методом поиска подстроки.
Допустим на вход будет подан микстейп или дорожка из фильма. В таком случае, максимум на что можно будет расчитывать - это сообщение о том, что в базе совпадений не найдено, хотя композиции наверняка в ней присутствуют.
В результате я хочу получить список строк, где есть совпадения и процент соответствия.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
24.06.2014, 19:04:59
    #38678940
Stupid_BOT
Stupid_BOT
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
CthulhUzzz,
делаешь из водной строки M = length(входная_строка) - N +1 строк.
Код: sql
1.
2.
3.
4.
5.
-- псевдокод
M = length(входная_строка) - N + 1
for z = 1 to M
  строка_z = substring(входная_строка, z, N)
next


Собираешь запрос
Код: sql
1.
2.
3.
4.
5.
6.
...
where
  instr( test_string, строка_1 ) != 0 or
  instr( test_string, строка_2 ) != 0 or
  ...
  instr( test_string, строка_M ) != 0;
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
24.06.2014, 19:33:41
    #38678959
S.G.
S.G.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
CthulhUzzzСтроки - аудио-отпечатки (По природе последовательность чисел, для удобства закодированные в строку).
...
Допустим на вход будет подан микстейп или дорожка из фильма. То есть, вы ищете совпадения *звука*, через строки?
Конкретнее, если есть мелодия из фильма в формате aac, и та же мелодия в формате mp3, вы рассчитываете найти похожесть, сравнивая побайтно?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
24.06.2014, 20:20:27
    #38678984
CthulhUzzz
CthulhUzzz
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
S.G.,

Именно, но сравнение конечно будет не аудио-потоков или файлов, а акустических отпечатков (Примерно также работает всем известный Shazam).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
25.06.2014, 10:56:59
    #38679400
alex564657498765453
alex564657498765453
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Выборка частично совпадающих строк
CthulhUzzzS.G.,

Именно, но сравнение конечно будет не аудио-потоков или файлов, а акустических отпечатков (Примерно также работает всем известный Shazam).

странно, я читал что подобные вещи работают немного по другому.

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

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

при опознавании при кусочке песни, мы выискиваем наш старт и строем этот отпечаток, и потом ищем точное совпадение!

там не возникает поиска что сдесь описан ТС

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

подобные вещи плохо распознают класическую музыку - по той же причине - трудно искать точки старта - там не прерывное звучание задействованых инструментов, а не как говорил задорнов - дунда дунда дунда дунда.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / MySQL [игнор отключен] [закрыт для гостей] / Выборка частично совпадающих строк / 20 сообщений из 20, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 373ms
Закрыть
start [/forum/topic.php?fid=47&tablet=1&tid=1834616]:
 0ms
get settings:
 6ms
get forum list:
 9ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 78ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 42ms
get tp. blocked users:
 1ms
others: 224ms
total:  373ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]