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

Question

История вопроса

У меня есть ограниченный словарный запас, содержащий, скажем, 10 символов [AJ].Что означают эти символы, не имеет отношения к вопросу.Это могут быть основы ДНК, фонемы, слова и т. Д.

Предмет - это последовательность символов.В этой задаче все предметы имеют одинаковую длину (скажем, 6).Например,

A C B A D J

У меня есть большая (5M) таблица, в которой содержится количество всех элементов длины 6, взятых из некоторых известных данных.Например,

A C B A D J     55
B C B I C F     923
A B C D E G     478

Учитывая новую последовательность с одним неизвестным символом, моя задача - угадать символ.В следующем примере отсутствующим символом является ? .

B C B ? C F

Простое решение угадать ? состоит в том, чтобы заглянуть в мою таблицу и найти элемент снаибольшее число, которое соответствует шаблону B C B ? C F

Вопросы

1. Что такое хорошая структура данных для хранения моей таблицы частот элементов, так что яобрабатывать пространство-время достаточно эффективно?Я предпочитаю использовать меньше памяти, если вычисления во время запроса разумны.(У меня будет много таких таблиц, и поэтому число 5M является лишь приблизительным.)

2. Какие детали реализации могут существенно повлиять на скорость обработки?

Вещи, о которых я думал:

1. Создайте строку из каждой последовательности и используйте регулярные выражения для сопоставления.Предостережение: 1. O (n) недопустимо.(2) регулярные выражения медленные.(3) Строки (по крайней мере в Java) раздуты.

2. Пусть Люсен справится с индексацией.Отключить оценку tfidf.Используйте фразу-поиск.Потенциально используйте значения счетчика для оценки, чтобы Lucene также позаботился о сортировке.

3. Используйте префикс и суффикс, чтобы индексировать каждый элемент.

4. Используйте дБ (вероятно, в памяти) со всеми данными в одном / отдельном столбце для обработки поиска.

---

Обновления

1. В моем реальном приложении я буду работать с последовательностями длиной 5,6,7,8,9,10, которые хранятся отдельно.Я упростил задачу, ограничив ее фиксированной длиной.Отсюда ограничение / предпочтение решения, которое использует меньше памяти.
2. Размер моего словаря может быть меньше 20.

Answer 1

Решение с помощью пытается представляется наилучшим: с числом появлений строк на листьях вы можете легко разработать функцию, которая будет возвращать все возможные строки с одним пропущенным символом за время O (log n), изатем вы просто перебираете это небольшое количество строк, ища максимальное количество вхождений.Если вы используете символы от A до Z, таких строк будет не более 26, поэтому повторение не займет много времени.

AFAIK, Lucene использует внутренний механизм для поиска по шаблону , так что вы можете объединить ваши символы, проиндексировать их с помощью KeywordAnalyzer (чтобы опустить стволовые) и затемпоиск как "ACB? DJ".Единственным ограничением здесь является то, что Lucene не может обрабатывать поиски с первым «?», Но вы можете обойти его, добавив один дополнительный символ в начале (просто хитрость, чтобы обойти проверки Lucene) или имея еще один индекс для обращенных слов (повысит производительностьдля слов с подстановочным знаком в качестве первого символа много).

И, наконец, если вам все равно придется сначала вычислить количество вхождений, вы можете использовать некоторые схемы машинного обучения, такие как деревья решений , для обработки всей работы.Были случаи, когда деревья решений использовались для сжатия базы данных и ускорения поиска, поэтому вы можете сделать то же самое.Используйте строки в качестве экземпляров, положение символов в качестве атрибутов и сами символы в качестве значений атрибутов.Затем запустите некоторый алгоритм, например C4.5 (вы можете использовать реализацию Weka под названием J48) с минимальной отсечкой и выполнить классификацию - алгоритм сделает все остальное!

Answer 2

На основании комментария, что будет только 1 неизвестный, вы можете сделать следующее:

Но ваши данные в хеш-таблице. Когда вам нужно найти шаблон, сгенерируйте все комбинации символов, так как ваш словарный запас ограничен, это будет означать, что вы сможете найти 20 шаблонов. Это звучит как хак, но, если учесть влияние других методов на производительность, трудно победить. Поиск в хеш-таблице равен O (1), 20 просмотров - также O (1).

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

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

Answer 3

Чтобы уникально охарактеризовать новую последовательность, необходимы две части информации: последовательность (строка) из пяти известных символов и позиция неизвестного символа. Если в вашем алфавите 10 символов, то может быть не более 10 ^ 5 = 100000 уникальных пятисимвольных строк.

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

---------
| BCBCF | --> { 0: <heap of symbols partially ordered by frequency>, ... }
---------

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

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

Answer 4

БД было бы простым решением, но другое решение - это дерево, где каждый узел выбирает один символ, а лист будет содержать массив возможных результатов и счетчиков.Тогда потребуется всего 5 шагов в дереве, чтобы соответствовать одной строке.Но создание дерева потребует N * C времени, где N - количество элементов, а C - количество символов в каждом элементе.Подстановочные знаки - это просто узел в дереве, который одновременно удаляет один символ из входных данных, но сохраняет возможные результаты без изменений.

Answer 5

Я был среди "всех, кто упускает очевидное" здесь.

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

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

---

Вот мой старый (и плохой) ответ.

Я бы поместил их в базу данных с несколькими объединенными индексами. Сколько вам решать.

Как минимум, у меня было бы 2. У меня был бы индекс на (col1, col2, col3, col4, col5, col6) и (col4, col5, col6, col1, col2, col3). Это будет означать, что, независимо от того, какой столбец отсутствует, будет способ получить ваши данные и просмотреть только максимум 1/1000 записей. Если хотите, вы можете вместо этого индексировать (col1, col2, col3, col4, col5, col6), (col3, col4, col5, col6, col1, col2) и (col5, col6, col1, col2, col3, col4), чтобы ограничить поиск до 1/10000 данных. Это использует вдвое больше памяти, но в 10 раз быстрее. (Предупреждение, я не буду гарантировать, что MySQL успешно определит, какой индекс он должен использовать. Я надеюсь, что другие базы данных сделают это правильно, но не проверили его.)

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