Считать при сжатии в LZW?

Question

Примечание. Это неправильное использование для сжатия LZW. Я просто играю с этим.

Вопрос

Можно ли за один проход также обновить счетчики частоты элементов внутри словаря?

Моя реализация

import sys
from collections import defaultdict
import re

# The silliest string!
inputString = "this is the first sentence in this book the first sentence is really the most interesting the first sentence is always first"
inputString = inputString.lower().split()

StringTable = defaultdict(int)
FreqTable = defaultdict(int)

def DoPass():
    global inputString
    global StringTable
    global FreqTable

    print ""
    print "INPUT STRING:"
    print inputString

    CODE = 256

    STRING = inputString[0]

    output = []

    StringTable[STRING] = CODE
    CODE += 1

    total = len(inputString)

    for i in range(1, total):
        WORD = inputString[i]

        if STRING + " " + WORD in StringTable:
            STRING += " " + WORD
        else:
            if STRING in StringTable:
                output.append(str(StringTable[STRING]))
            else:
                output.append(STRING)
            StringTable[STRING + " " + WORD] = CODE
            CODE += 1
            STRING = WORD

    StringTable[STRING] = CODE
    CODE += 1
    output.append(str(StringTable[STRING]))

    print ""
    print "OUTPUT STRING:"
    print output

    print ""
    print "Dictionary Built..."
    for i in sorted(StringTable.keys(), key=lambda x: len(x)):
        print i, StringTable[i]

    print ""
    print "Frequencies:"
    for i in sorted(FreqTable.keys(), key=lambda x: len(x)):
        print i, FreqTable[i]

def main():
    DoPass()

if __name__ == "__main__":
    main()

Выход

INPUT STRING:
['this', 'is', 'the', 'first', 'sentence', 'in', 'this', 'book', 'the', 'first', 'sentence', 'is', 'really', 'the', 'most', 'interesting', 'the', 'first', 'sent
ence', 'is', 'always', 'first']

OUTPUT STRING:
['256', 'is', 'the', 'first', 'sentence', 'in', '256', 'book', '259', 'sentence', 'is', 'really', 'the', 'most', 'interesting', '265', 'is', 'always', '275']

Dictionary Built...
this 256
first 275
is the 258
in this 262
this is 257
book the 264
the most 269
this book 263
is always 273
is really 267
the first 259
really the 268
sentence in 261
sentence is 266
always first 274
first sentence 260
interesting the 271
most interesting 270
the first sentence 265
the first sentence is 272

Frequencies:
#### I am trying to fill this

Я хочу заполнить FreqTable частотами всех найденных паттернов. Я не поместил свой метод здесь по понятным причинам - он не работает, и это дает мне неправильные счета. Любые предложения о том, возможно ли это, было бы здорово.

Answer 1

Не уверен, что понял ваш вопрос.Если вам просто нужна таблица частот, то это должно быть просто: каждый раз, когда вы находите паттерн, вы просто добавляете +1 к его частотному счетчику.Таким образом, настоящая проблема должна заключаться в том, чтобы найти шаблон.

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

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

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