Вопросы Теги

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

История проблемы

У меня ограниченный словарь, содержащий, скажем, 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

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

Вопросы

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

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

Что я придумал:

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

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

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

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

Обновления

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