Обсуждение участника:KirillKutirev — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Алгоритм Хаффмана за O(n) .)
м (Пример)
 
(не показано 25 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
== Алгоритм Хаффмана за  <tex> O(n) </tex>. ==
 
== Алгоритм Хаффмана за  <tex> O(n) </tex>. ==
  
У нас есть массив частот (массив, в котором хранится число вхождений каждого символа в строку), отсортированный по возрастанию, нужно построить по нему код Хаффмана за <tex> O(n) </tex> (но если массив не отсортирован, то это можно сделать цифровой сортировкой за  <tex> O(n) </tex> что не ухудшит решение).
+
У нас есть массив частот (массив, в котором хранится число вхождений каждого символа в строку), отсортированный по возрастанию, нужно построить по нему код Хаффмана за <tex> O(n) </tex> (если массив не отсортирован, то это можно сделать, например,[[Цифровая_сортировка | цифровой сортировкой]] за  <tex> O(n) </tex>, что не ухудшит асимптотику).
  
Идея алгоритма заключается в том, чтобы создать такую очередь с приоритетами, из которой можно было бы доставать два минимума за <tex> O(1) </tex>, после чего в эту же очередь с приоритетами положить их сумму за <tex> O(1) </tex>. У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных (т.е. на каждом последующем шаге мы выбираем два минимума из элементов больших, чем на предыдущем шаге).  
+
Идея алгоритма заключается в том, чтобы создать такую [[Дискретная_математика,_алгоритмы_и_структуры_данных#.D0.9F.D1.80.D0.B8.D0.BE.D1.80.D0.B8.D1.82.D0.B5.D1.82.D0.BD.D1.8B.D0.B5_.D0.BE.D1.87.D0.B5.D1.80.D0.B5.D0.B4.D0.B8 | очередь с приоритетами]], из которой можно было бы доставать два минимума за <tex> O(1) </tex>, после чего в эту же очередь с приоритетами положить их сумму за <tex> O(1) </tex>. У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных (т.е. на каждом последующем шаге мы выбираем два минимума из элементов больших, чем на предыдущем шаге).  
Тогда на каждой итерации мы будет выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее.  
+
На каждой итерации мы будет выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее.  
  
 
У нас есть три варианта возможных пар минимумов :
 
У нас есть три варианта возможных пар минимумов :
Строка 11: Строка 11:
 
# Два первых элемента второго массива.
 
# Два первых элемента второго массива.
  
В первом варианте мы просто дописываем сумму в конец второго массива. Во втором варианте мы вычеркиваем первый элемент из второго массива и добавляем его сумму с первым элементом первого массива в конец второго. Ну и в третьем варианте, мы вычеркиваем два первых элемента второго массива и добавляем их сумму в конец этого массива. Если в первом массиве элементы закончились, а во втором осталось больше одного элемента, то они меняются ролями.
+
В первом варианте мы просто дописываем сумму в конец второго массива. Во втором варианте мы вычеркиваем первый элемент из второго массива и добавляем его сумму с первым элементом первого массива в конец второго. Ну и в третьем варианте, мы вычеркиваем два первых элемента второго массива и добавляем их сумму в конец этого массива.Если в первом массиве элементы закончились, а во втором осталось больше одного элемента, то они меняются ролями.
  
В алгоритме <tex> n </tex> итерации, так как на каждом шаге количество элементов  уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время.
+
На каждом шаге количество элементов  уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, следовательно, программа делает ровно <tex>n</tex> итераций.
 +
 
 +
==Пример==
 +
Для примера возьмем строку "абракадабра".
 +
 
 +
{| class="wikitable"
 +
! Буква || д || к || б || р || а
 +
|-
 +
| Массив 1 || 1 || 1 || 2 || 2 || 5
 +
|-
 +
| Массив 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
 +
|}
 +
 
 +
На первом шаге два минимальных элемента - это первые две ячейки первого массива. Их сумму сохраняем во второй массив.
 +
{| class="wikitable"
 +
| Массив 1 || used || used || 2 || 2 || 5
 +
|-
 +
| Массив 2 || 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
 +
|}
 +
 
 +
На втором шаге снова суммируются первые две ячейки первого массива(нам все равно что взять, первый элемент второго массива или второй элемент первого).
 +
{| class="wikitable"
 +
| Массив 1 || used || used || used || used || 5
 +
|-
 +
| Массив 2 || 2 || 4 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
 +
|}
 +
 
 +
На третьем шаге два минимальных элемента - это первые две ячейки второго массива.
 +
{| class="wikitable"
 +
| Массив 1 || used || used || used || used || 5
 +
|-
 +
| Массив 2 || deleted || deleted || 6 || <tex>\infty</tex> || <tex>\infty</tex>
 +
|}
 +
 
 +
На четвертом шаге складываются две оставшиеся ячейки.
 +
{| class="wikitable"
 +
| Массив 1 || used || used || used || used || used
 +
|-
 +
| Массив 2 || deleted || deleted || deleted || 11 || <tex>\infty</tex>
 +
|}
 +
 
 +
==Реализация==
 +
Поскольку мы не ограничены по памяти, очень удобно использовать вместо двух одномерных массивов один двумерный. Это избавит код от громоздких "if".
 +
  n // количество элементов
 +
  s1 = 0, s2 = 1 // указатели на строки, которые выполняют функции первого и второго массивов в описании алгоритма
 +
  h1 = 0, h2 = 0 // указатели на первый элемент первой строки и второй строки соответственно
 +
  t1 = n, t2 = 0 // указатели на ячейки массивов сразу после последнего элемента в этих массивах
 +
  check = 0 // считает на сколько стало меньше элементов
 +
   
 +
  class vert{ // класс - лист дерева, которое, по сути, строится в коде хаффмана
 +
  public:
 +
    val // значение кодового символа {0,1}
 +
    w // сумма в данном поддереве
 +
    left // самый левый элемент начального массива в данном поддереве, чтобы упростить поиск при спуске
 +
    check // проверка на то, является ли данный лист самым нижним в дереве
 +
    *nextl, *nextr // указатели на левого и правого детей
 +
    vert(){
 +
      check = 1;
 +
      val = 0;
 +
    }
 +
  };
 +
 
 +
  sum = vert[logMAXN][MAXN+1] //  элементы w каждой ячейки равны "бесконечности"
 +
  temp = vert // переменная, на которую ссылаются самые нижние листья дерева
 +
  temp.check = -1
 +
 +
  make(int str1, int str2, int pos1, int pos2)// функция, которая суммирует, задает указатели и значения переменных val и left
 +
    sum[s2][t2].w = sum[str1][pos1].w + sum[str2][pos2].w
 +
    sum[s2][t2].nextl = &sum[str1][pos1]
 +
    sum[s2][t2].nextr = &sum[str2][pos2]
 +
    sum[s2][t2].left = min(sum[str1][pos1].left,sum[str2][pos2].left)
 +
    sum[str1][pos1].val = 0
 +
    sum[str2][pos2].val = 1
 +
 
 +
  coding(sum)
 +
    '''while''' check < n
 +
      '''while''' h1 < t1 // проходим по массиву, выполняющему роль первого; внутри этого цикла мы ищем минимумы и записываем суммы
 +
          '''if''' sum[s1][h1].w < sum[s2][h2].w
 +
              '''if''' sum[s1][h1+1].w <= sum[s2][h2].w
 +
                make(s1,s1,h1,h1+1)
 +
                '''if'''(t2 - h1 == 2)
 +
                  sum[s2][t2].w -= sum[s1][h1+1].w
 +
                  sum[s2][t2].nextr = &temp;                    
 +
                h1 += 2
 +
              '''else'''
 +
                make(s1,s2,h1,h2)
 +
                h1++
 +
                h2++
 +
              t2++
 +
          '''else'''
 +
              '''if''' sum[s1][h1].w < sum[s2][h2+1].w
 +
                make(s2,s1,h2,h1)
 +
                h1++
 +
                h2++
 +
              '''else'''
 +
                make(s2,s2,h2,h2+1)
 +
                h2+=2
 +
              t2++
 +
          check++ // учитываем то, что элементов стало на 1 меньше
 +
      s1 = s2 // строки меняются ролями, соответственно все их параметры тоже
 +
      h1 = h2
 +
      t1 = t2
 +
      s2++
 +
      h2 = t2 = 0
 +
    return sum[s1][h1] // возвращает вершину дерева, получить код каждого символа можно получить за logn

Текущая версия на 23:28, 7 января 2014

Алгоритм Хаффмана за [math] O(n) [/math].

У нас есть массив частот (массив, в котором хранится число вхождений каждого символа в строку), отсортированный по возрастанию, нужно построить по нему код Хаффмана за [math] O(n) [/math] (если массив не отсортирован, то это можно сделать, например, цифровой сортировкой за [math] O(n) [/math], что не ухудшит асимптотику).

Идея алгоритма заключается в том, чтобы создать такую очередь с приоритетами, из которой можно было бы доставать два минимума за [math] O(1) [/math], после чего в эту же очередь с приоритетами положить их сумму за [math] O(1) [/math]. У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных (т.е. на каждом последующем шаге мы выбираем два минимума из элементов больших, чем на предыдущем шаге). На каждой итерации мы будет выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее.

У нас есть три варианта возможных пар минимумов :

  1. Оба элемента из первого массива.
  2. Первый элемент первого массива и первый элемент второго массива.
  3. Два первых элемента второго массива.

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

На каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, следовательно, программа делает ровно [math]n[/math] итераций.

Пример

Для примера возьмем строку "абракадабра".

Буква д к б р а
Массив 1 1 1 2 2 5
Массив 2 [math]\infty[/math] [math]\infty[/math] [math]\infty[/math] [math]\infty[/math] [math]\infty[/math]

На первом шаге два минимальных элемента - это первые две ячейки первого массива. Их сумму сохраняем во второй массив.

Массив 1 used used 2 2 5
Массив 2 2 [math]\infty[/math] [math]\infty[/math] [math]\infty[/math] [math]\infty[/math]

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

Массив 1 used used used used 5
Массив 2 2 4 [math]\infty[/math] [math]\infty[/math] [math]\infty[/math]

На третьем шаге два минимальных элемента - это первые две ячейки второго массива.

Массив 1 used used used used 5
Массив 2 deleted deleted 6 [math]\infty[/math] [math]\infty[/math]

На четвертом шаге складываются две оставшиеся ячейки.

Массив 1 used used used used used
Массив 2 deleted deleted deleted 11 [math]\infty[/math]

Реализация

Поскольку мы не ограничены по памяти, очень удобно использовать вместо двух одномерных массивов один двумерный. Это избавит код от громоздких "if".

 n // количество элементов
 s1 = 0, s2 = 1 // указатели на строки, которые выполняют функции первого и второго массивов в описании алгоритма
 h1 = 0, h2 = 0 // указатели на первый элемент первой строки и второй строки соответственно
 t1 = n, t2 = 0 // указатели на ячейки массивов сразу после последнего элемента в этих массивах
 check = 0 // считает на сколько стало меньше элементов
   
 class vert{ // класс - лист дерева, которое, по сути, строится в коде хаффмана
 public:
   val // значение кодового символа {0,1}
   w // сумма в данном поддереве
   left // самый левый элемент начального массива в данном поддереве, чтобы упростить поиск при спуске
   check // проверка на то, является ли данный лист самым нижним в дереве
   *nextl, *nextr // указатели на левого и правого детей
   vert(){
     check = 1;
     val = 0;
   }
 };
 
 sum = vert[logMAXN][MAXN+1] //  элементы w каждой ячейки равны "бесконечности"
 temp = vert // переменная, на которую ссылаются самые нижние листья дерева
 temp.check = -1

 make(int str1, int str2, int pos1, int pos2)// функция, которая суммирует, задает указатели и значения переменных val и left
   sum[s2][t2].w = sum[str1][pos1].w + sum[str2][pos2].w
   sum[s2][t2].nextl = &sum[str1][pos1]
   sum[s2][t2].nextr = &sum[str2][pos2]
   sum[s2][t2].left = min(sum[str1][pos1].left,sum[str2][pos2].left)
   sum[str1][pos1].val = 0
   sum[str2][pos2].val = 1
 
 coding(sum)
   while check < n
     while h1 < t1 // проходим по массиву, выполняющему роль первого; внутри этого цикла мы ищем минимумы и записываем суммы
          if sum[s1][h1].w < sum[s2][h2].w
              if sum[s1][h1+1].w <= sum[s2][h2].w
                make(s1,s1,h1,h1+1)
                if(t2 - h1 == 2)
                  sum[s2][t2].w -= sum[s1][h1+1].w
                  sum[s2][t2].nextr = &temp;		                     
                h1 += 2
              else
                make(s1,s2,h1,h2)
                h1++
                h2++
              t2++ 
          else
              if sum[s1][h1].w < sum[s2][h2+1].w
                make(s2,s1,h2,h1)
                h1++
                h2++
              else
                make(s2,s2,h2,h2+1)
                h2+=2
              t2++
          check++ // учитываем то, что элементов стало на 1 меньше
     s1 = s2 // строки меняются ролями, соответственно все их параметры тоже
     h1 = h2
     t1 = t2
     s2++
     h2 = t2 = 0
   return sum[s1][h1] // возвращает вершину дерева, получить код каждого символа можно получить за logn