48
правок
Изменения
Pseudocode debug
'''double''' right
'''voidSegment''' [] defineSegments(letters: '''char'''[m], probability: '''double'''[m]):
'''Segment'''[m] segment
'''double''' l = 0
segment[letters[i]].left = l
segment[letters[i]].right = l + probability[i]
'''return''' segment
'''double''' arithmeticCoding(s: '''char'''[n]):
'''Segment'''[m] segment = defineSegments(letters, probability)
'''double''' left = 0
'''double''' right = 1
'''char''' character
'''voidSegment''' [] defineSegments(letters: '''char'''[n], probability: '''double'''[n]):
'''Segment'''[m] segment
'''double''' l = 0
segment[i].right = l + probability[i]
segment[i].character = letters[i]
'''return''' segment
'''string''' arithmeticDecoding(code: '''double''', n: '''int'''):
'''Segment'''[m] segment = defineSegments(letters, probability)
'''string''' s = ""
'''for''' i = 0 '''to''' n - 1
'''for''' j = 0 '''to''' m - 1
'''if''' code >= segment[j].left '''and''' code < segment[j].right ''<font color=green>// segment {{---}} массив, заполненный в результате выполнения метода defineSegments</font>''
s += segment[j].character
code = (code – segment[j].left) / (segment[j].right – segment[j].left)
'''Замечание:''' кодировщику и декодировщику должно быть известно, когда завершать работу. Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.
'''Замечание:''' Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера {{---}} поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, <tex>\dfrac{1}{3}</tex>), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число. В такой реализации вероятность встречи символа представляется в виде дроби, числитель которой представляет количество использований символа в тексте, знаменатель {{---}} длину <tex>n</tex> исходного текстарационального числа. Поскольку в каждой итерации будет переход из текущего отрезка в один из его <tex>m</tex> подотрезков, кратных по длине <tex>n</tex>, а всего итераций <tex>n</tex>, в конечном результате в качестве знаменателя знаменатель дроби будет <tex>n^{n}не превысит </tex>, а числитель можно найти, рассматривая отрезок <tex>[0; n^{n})</tex> на первой итерации.
== Пример работы ==
||proof=Введём следующие обозначения:
*<tex>l</tex> {{---}} длина текста;,*<tex>n</tex> {{---}} размер алфавита;,*<tex>f_i</tex> {{---}} частота встречаемости символа;,
*<tex>p_i</tex> {{---}} вероятность вхождения символа.
