Сокращение использования памяти при сохранении всех подпоследовательности набора последовательностей

Обновить

December 2018

Просмотры

312 раз

4

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

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

Чтобы было ясно, о чем я говорю, предположим, что мы имеем последовательность:

#1=(A B C D)

Подпоследовательности являются:

#2=()
#3=(A)
#4=(A B)
#5=(A B C)
#6=(A B C D)
#7=(B)
#8=(B C)
#9=(B C D)
#10=(C)
#11=(C D)
#12=(D)

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

(defun subseqs-of-length (length sequence)
  (if (< (length sequence) length)
      nil
      (loop for start from 0 to (- (length sequence) length)
           collect (subseq sequence start (+ start length)))))

(defun subseqs-of-length-< (length sequence)
  (loop for len from 1 to (1- length)
     append (subseqs-of-length len sequence)))

(defun all-subseqs (sequence)
    (subseqs-of-length-< (1+ (length sequence)) sequence))

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

Самый очевидный способ , которым я могу думать , чтобы сохранить память, чтобы разделить кучу списочного состава; Например, вы можете создать список 11 по (cons 'c '#12#), список 9 по (cons 'b '#11#), список 8, (cons 'b '#10#и так далее. Было бы еще лучше , если выход нескольких вызовов all-subseqsможет разделить структуру. Но я не могу думать элегантно , чтобы написать это.

Мой вопрос заключается в два раза:

  1. Есть элегантный способ , чтобы написать all-subseqsтак , что его результаты будут делить структуру , что путь?
  2. Мне пришло в голову, что это может быть проще для создания подпоследовательности наивным и написать функцию, чтобы сжать результаты и запустить его периодически. Разве это не глупая идея?
  3. Есть еще более эффективный способ памяти для хранения этой подпоследовательности и доступа / обновлять значения, связанные с ними? Возможно, что-то с помощью массивов, или другая структура данных вместо хэш-таблицы?

3 ответы

2

Каков минимальный объем информации, необходимый для восстановления подпоследовательности?

Как насчет последовательности, индекс начального и конечного индекса. Хранить начало / конец индексы в двумерной хэш-таблицы (хэш-таблицу хэш-таблицы), или массив 2-d. Тогда писать функции, чтобы сделать работу по этой структуре данных (реконструировать подпоследовательность заданную последовательность, индекс начала, и конечный индекс, и т.д.).

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

И если каждый элемент в списке является символом, затем «а в одном списке будет экв (доля же MEM местоположение) как» а в другом списке. Что я думаю, что означает, что вы можете получить O (N) роста хранения + независимо инкрементный рост происходит путем добавления ссылки на структуры данных.

1

Просто ответить на первый вопрос:

(defun all-subseqs (list)
  (loop :for sublist := list :then (butlast sublist)
        :while sublist
        :nconc (maplist #'identity sublist)))

Это позволяет все подпоследовательности, которые имеют ту же структуру, хвост акций.

Для приложения вы обрисовать, там должно быть лучше структура данных. Граф дерева , показанные Йохан выглядят многообещающими.

2

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

Подсчет дерево просто обычное дерево дополнена информацией частоты в каждом узле. Каждый узел в дереве может иметь несколько детей, Infact все символов в алфавите. Выделяя для всех может быть довольно расточительно, так просто использовать простой связанный список как ключ-значение, и пусть следующий символ в последовательности быть ключом, с узлом, представляющим это значение существа. В этой схеме, корневой узел представляет пустую последовательность. Это, конечно, позволяет вычислить P (C | A, B), глядя вверх путь A, B, C в дереве и деления частоты A, B, C на FREQ. АВ, чтобы получить базовую оценку ОМП.

(defstruct lm-tree-node
  (total 0)
  (children (make-lash)))

(defun add-sequence (seq lm-root &optional (count 1))
  (let ((children (lm-tree-node-children lm-root)))
    (incf (lm-tree-node-total lm-root) count)
    (let ((child
           (get-or-add-lash (first seq) children (make-lm-tree-node))))
      (if (rest seq)
          (add-sequence (rest seq) child count)
        (incf (lm-tree-node-total child) count)))))

Для того, чтобы поместить данные в дереве просто взять все последовательности, начните с корнем и прибавить 1 к частоте всех узлов , как вы ходить ваши последовательности. Приведенный выше код от проекта , в котором я сделал модель языка для декодера Hidden Markov Model. Это на GitHub , если какой - то тусклый ОТТ посмотреть. А «наброситься» -стол это просто общий ключ-значение связанного списка , который может трансформироваться в хэш-таблицу , если это необходимо. Поскольку граф дерево может иметь очень много узлов, важно , что они имеют небольшой объем памяти, и хэш-таблицы в каждом узле может быть и речи. Как правило , только верхние узлы в дереве графа будет иметь много (сто или около того ) детей, так что это выгодно , если они могут использовать хэш-таблицу.

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

(defun sentence-to-n-grams (sentence n lm-root)
  (let ((buffer (make-fast-queue :size n :buffer (make-array n))))
  (loop
      for word fixnum in sentence
      for seq = (fast-queue-to-list (fast-enqueue buffer word))
      when (>= (length seq) n)
      do (add-sequence seq lm-root)
      finally (loop
                  for x on (rest seq)
                  do (add-sequence x lm-root)))))