Xpoint
   [напомнить пароль]

Быстрый поиск максимального совпадения

Метки: [без меток]
[арх]
2011-04-12 11:11:15 [обр] Thirteensmay(0/157)[досье]
Дан большой список строк (30 млн), каждая длинной 10 символов (кириллица, латиница, цифры, без учета регистра). Дается строка для поиска, необходимо найти ее в списке, либо если нет - найти несколько наиболее похожих ей строк, т.е. отличающихся как можно меньшим количеством символов. Проблема в том что поиск должен быть быстрым, порядка 0.1 сек, машинка конечно может быть весьма мощной, но не мегамонстр. Пока не пробовал, но чую что тупой перебор будет медленным, есть ли какие варианты оптимизации ?
спустя 10 минут [обр] Евгений Седов aka KPbIC(0/176)[досье]
Отличающиеся символы могут быть в любых позициях или только в конечных (ищем совпадение от начала)?
спустя 1 минуту [обр] Thirteensmay(0/157)[досье]
В любых
спустя 33 минуты [обр] Евгений Седов aka KPbIC(0/176)[досье]
сообщение промодерировано
Строка поиска тоже 10 символов?
спустя 27 минут [обр] Thirteensmay(0/157)[досье]
Да, тоже 10. Пока приходит идея только разделять список на партиции, размещать их в памяти и каждую перебирать в отдельном потоке, оптимизация никакая что то не придумывается. Сам исходный список можно представить как понадобится.
спустя 46 минут [обр] Филипп Ткачев(0/112)[досье]
Превращение всего хозяйства в байтовый массив и сравнение с использованием унарных битовых операций с построением пирамиды результатов начиная с определенного количества совпадений. Если весь массив разместить в памяти и написать код на C, будет вполне производительно.
спустя 38 минут [обр] Thirteensmay(0/157)[досье]
Ну, с распоточиванием и оптимизацией полного перебора понятно, но это всетаки полный перебор 300 мегабайт массива, и это надо успеть за 0.1 сек, чето по моему пожет непопереть. Интересно именно какая нибудь хитрость, типа индексов или простраивания цепочек родства, или еще чтото в этом духе, есть ли какие нибудь мысли на эту тему ?
спустя 1 минуту [обр] Евгений Седов aka KPbIC(0/176)[досье]
сообщение промодерировано
Thirteensmay[досье] Каков критерий для формирования набора похожих записей? — в случае отсутствия точного совпадения всегда ищется какое-то фиксированное число похожих записей или есть порог на количество несовпадений, при котором поиск похожих записей оканчивается неудачей?
спустя 1 час 15 минут [обр] Thirteensmay(0/157)[досье]
Похожие значит отличающиеся как можно меньшим количеством символов в любых позициях, наиболее близкие те у которых в любой позиции стоит один любой другой символ, мене похожие если различие по 2 любым позициям и т.п. В случае отсутствия точного совпадения надо найти 100 наиболее близких, ну или хотя бы одно, но если одно то оно должно быть случайным, различаться при повторном аналогичном поиске, т.е. при повторе должно быть другое наиболее близкое.
спустя 3 часа 42 минуты [обр] Евгений Седов aka KPbIC(0/176)[досье]
Thirteensmay[досье] Набор поисковых строк фиксирован или поисковые строки все время разные?
спустя 3 часа 32 минуты [обр] Thirteensmay(0/157)[досье]
Та строка для которой надо найти соответствия поступает 3-10 раз в сек, каждый раз разная, а вот список эталонных строк среди которых ищутся соответствия абсолютно статичен. Я вам так скажу, может понятнее будет, есть база кодов, на вход системы с оптического распознавателя поступает распознанный код проходящего объекта, но он может быть распознан с ошибкой, по этому по ТЗ его надо сопоставить с базой кодов, а если не совпал то выдать предупреждение и список наиболее на него похожих.
спустя 2 часа 33 минуты [обр] Евгений Седов aka KPbIC(0/176)[досье]
А что, если из 30 млн построить граф, вершины которого расположены на уровнях, соответствующих индексу символа в строке. Вначале искать полное совпадение, потом -1, -2 и т.д., каждый раз проходя с первого уровня вниз. При поиске строки с возможным единственным несовпадением, на 3 уровне можно уже будет отсечь цепи с двумя несовпадениями.
спустя 20 часов [обр] Thirteensmay(0/157)[досье]
Перефразируйте пожалуйста, а то что то я вас не пойму, как именно ? пример ?
спустя 2 часа 18 минут [обр] Евгений Седов aka KPbIC(0/176)[досье]

Допустимые символы: A, B, C, D; длина строки — 4 символа.
Имеем строки:
ABBC
ACDA
DBBC
DCBA

[i]ABCD
1AD
2ABAC
DBDC
3DCBACD
DBB
ABB
4DCBAABBC
ACDADBBC

Thirteensmay[досье] Так хоть немного яснее?

спустя 2 часа 32 минуты [обр] Thirteensmay(0/157)[досье]
Насколько я понимаю имеем набор массивов, для каждой позиции каждой буквы, в массивах располагаются начала существующих строк оканчивающиеся соответствующей буквой в соответствующей позиции. Увеличение расхода памяти получается приемлемое, грубо говоря раза в 3. Но каков алгоритм поиска ?
спустя 19 минут [обр] Евгений Седов aka KPbIC(0/176)[досье]
сообщение промодерировано

Я не уверен насчет массивов. В реализации это скорее будут связные списки и в ячейках будут храниться вертикальные указатели на предыдущий уровень, а не строки.

Допустим, строка поиска: CBBC.

Сначала ищем точное соответствие. Начинаем со строки 1. Ячейка "С" пуста. Дальнейший поиск не имеет смысла, попытка провалилась.

Теперь ищем варианты с одним несоответствием. В строке 1 собираем все непустые ячейки [A,D]. Идем во вторую строку. В этой строке нас интересует только колонка "B", так как лимит на несовпадения уже исчерпан: [AB,DB].

Переходим в третью строку. Из имеющихся [AB,DB] остаются [ABB,DBB].

Переходим в последнюю, четвертую строку, в колонку "С". Из имеющихся [ABB, DBB] остаются [ABBC,DBBC].

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

Обратите внимание на то, что происходит в случае, если строки незначительно различаются в последних позициях. Например ABCD vs ABCB. У них будет различаться только один указатель, ведущий снизу вверх.

спустя 8 часов [обр] Thirteensmay(0/157)[досье]
Ну, вроде да, похоже на оно, спасибо ;) В принципе те же переборы с хранением промежуточного состояния, но количество переборов вроде значительно меньше и расходы по памяти не должны быть очень большими. Буду тестить.
Powered by POEM™ Engine Copyright © 2002-2005