3
правки
Изменения
м
→Реализация
dict[buffer + s[i]] = dict.length + 1 <font color=green>// добавляем слово в словарь</font>
buffer = "" <font color=green>// сбрасываем буфер</font>
'''if''' not (buffer is empty): <font color=green>// если буффер не пуст - этот код уже был, нужно его добавить в конец словаря</font>
last_ch = buffer.peek() <font color=green>// берем последний символ буффера, как "новый" символ</font>
buffer.pop() <font color=green>// удаляем последний символ из буфера</font>
ans.push({dict[buffer], last_ch}) <font color=green>// добавляем пару в ответ</font>
'''return''' ans
</code>
| <tex>\varnothing</tex> || <tex>abacababacabc</tex> || {{---}} || <tex>\langle 0, a \rangle</tex> || В словаре ничего не нашлось, вместо номера в словаре указываем <tex>0</tex>
|-
| <tex>a</tex> || <tex>bacababacabcbbacababacabc</tex> || {{---}} || <tex>\langle 0, b \rangle</tex> ||
|-
| <tex>a</tex>, <tex>b</tex> || <tex>acababacabc</tex> || <tex>a</tex> || <tex>\langle 1, c \rangle</tex> || Нашелся префикс <tex>a</tex> (слова в словаре нумеруются с <tex>1</tex>), добавляем <tex>ac</tex>
* [http://mf.grsu.by/UchProc/livak/en/po/comprsite/theory_lz77.html Алгоритм LZ77]
* [http://www.binaryessence.com/dct/en000140.htm Lempel-Ziv-78]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия]]
