Блог

Я пытаюсь реализовать алгоритм кодирования Хаффмана, но продолжаю получать эту ошибку из-за сравнений для очереди приоритетов.
Мой код:

 class Node(object):
    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right
    def children(self):
        return(self.left, self.right)
    def __lt__(self,other):
        return 0

def create_tree(count):
    print(count)
    priority = queue.PriorityQueue()
    for value in count:
        priority.put(value)
    while priority.qsize() > 1:
        one, two = priority.get(), priority.get()
        node = Node(one, two)
        priority.put((one[0] two[0], node))
    return priority.get()
  

Я пробовал несколько попыток использования _lt_ в моем классе HuffmanNode, но всегда заканчиваю тем, что не могу сравнить ‘str’ с ‘Node’, ‘int’ или ‘tuple’. Мне интересно, возможно ли это сделать, и любые предложения будут оценены.

Редактировать: Также для create_tree учитывается список кортежей, который выглядит как:
[(1, 'a'), (1, 'b'), (2, 'c')]

Код, который должен выдавать ошибку:

 [(1, 113), (1, 107), (1, 98), (1, 120), (1, 106), (1, 118), (1, 108), (1, 122), (1, 121), (1, 100), (1, 87), (1, 70), (1, 10), (2, 84), (2, 117), (2, 99), (2, 119), (2, 102), (2, 109), (2, 97), (2, 46), (3, 110), (3, 112), (4, 114), (4, 115), (4, 116), (4, 103), (5, 104), (5, 101), (7, 105), (8, 111), (18, 32)]
  

Также понял, что изменил свой код, чтобы он использовал значения ASCII, а не строки, но я получаю ту же ошибку, будь то ‘int’ или ‘str’

Это взято прямо из документации для PriorityQueue :

Сначала извлекаются записи с наименьшим значением (запись с наименьшим значением — это та, которая возвращается sorted(list(entries))[0]) . Типичным шаблоном для записей является кортеж в виде: (priority_number, data) .

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

Приведенный ими пример кода является:

 from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)
  

Используя пример, который вы предоставили для count = [(1, 'a'), (1, 'b'), (2, 'c')] :

 def create_tree(count):
    print(count)
    priority = queue.PriorityQueue()
    for value in count:
        priority.put(value)
    while priority.qsize() > 1:
        one, two = priority.get(), priority.get()  # one == (1, 'a'); two == (1, 'b')
        node = Node(one, two)  # node == Node(left=(1, 'a'), right=(1, 'b'))
        priority.put((one[0] two[0], node))  #  (2, Node(left=(1, 'a'), right=(1, 'b'))  <== error here
    return priority.get()
  

Когда ваш код добавляет (2, Node(left=(1, 'a'), right=(1, 'b')) к PriorityQueue другому элементу в очереди, он (2, 'c') имеет тот же приоритет, поэтому для сортировки используется элемент данных.

Итак, вам нужно либо явно игнорировать сортировку по данным (смотрите Пример документации выше для получения некоторых указаний), либо определить, как 'c' следует сортировать относительно Node(left=(1, 'a'), right=(1, 'b')) и реализовать это. Например, если вы всегда хотите Node сортировать last относительно какого-либо другого типа данных:

 def __lt__(self, other):
    return True

def __gt__(self, other):
    return False
  

Или наоборот:

 def __lt__(self, other):
    return False

def __gt__(self, other):
    return True
  

Или что-то более сложное?

При реализации __lt__() вы создаете сравнение для Node < int , но не для int < Node .

Чтобы получить это, нам нужно отменить операцию:

У этих методов нет версий с заменой аргументов (которые используются, когда левый аргумент не поддерживает операцию, а правый аргумент поддерживает); скорее, __lt__() и __gt__() являются отражением друг друга, __le__() и __ge__() являются отражением друг друга, а __eq__() и __ne__() — их собственным отражением.

Документация по модели данных Python

Другими словами, при вычислении, B < A т.Е. B.__lt__(A) и B не определяет подходящий __lt__() метод, он использует A.__gt__(B) вместо этого.

Чтобы исправить это, добавьте следующее в свой Node класс:

 def __gt__(self,other):
    return 0 # or something else intelligent