Изменения
Нет описания правки
== Корректность алгоритма Хаффмана для <tex>n</tex>-ичной системы счисления ==
Доказательство аналогично тому,что представлено в теме [[Алгоритм Хаффмана]].Только вместо двух символом с минимальными частотами надо брать <tex>n</tex> символов с минимальными частотами(по алгоритму вес символа также может равняться 0)
==Задача о подсчете числа битов==
Имеются частоты символов,встречающихся в исходном тексте.Необходимо подсчитать суммарное число бит,необходимое для кодирования этого текста.
Возьмем <tex>sum=0</tex>.На каждом шаге выбираем две наименьшие частоты,объединяем их сумму в одну частоту и добавляем в список вместо двух исходных.Новую частоту прибавляем к <tex>sum</tex> с присваиванием.Шаги заканчиваются тогда,когда в списке останется только одна частота.
В-итоге,<tex>sum</tex>-число бит необходимое для кодирования этого текста
Псевдокод алгоритма:
'''int''' DamerauLevenshteinDistance('''char''' S[1..M], '''char''' T[1..N])
'''int''' d[0..M, 0..N]
'''int''' i, j, cost
''// База динамики''
'''for''' i '''from''' 0 '''to''' M
d[i, 0] = i
'''for''' j '''from''' 1 '''to''' N
d[0, j] = j
'''for''' i '''from''' 1 '''to''' M
'''for''' j '''from''' 1 '''to''' N
''// Стоимость замены''
'''if''' S[i] == T[j] '''then''' replaceCost = 0
'''else''' replaceCost = 1
d[i, j] = minimum(
d[i-1, j ] + deleteCost, ''// удаление''
d[i , j-1] + insertCost, ''// вставка''
d[i-1, j-1] + replaceCost ''// замена''
)
'''if'''(i > 1 '''and''' j > 1
'''and''' S[i] == T[j-1]
'''and''' S[i-1] == T[j]) '''then'''
d[i, j] = minimum(
d[i, j],
d[i-2, j-2] + transposeCost ''// транспозиция''
)
'''return''' d[M, N]
