Código Huffman VS Código Hu – Tucker

Antes de fazer minha pergunta, deixe-me começar com meu entendimento das definições, para me impedir com mais confusão e também fornecer alguns antecedentes.

O Código Huffman é o código binário induzido a partir de uma árvore binária, construída pelo algoritmo de Huffman.
O código Hu – Tucker é o código binário induzido a partir de uma árvore de pesquisa alfabética.
De acordo com a Wikipedia (consulte o parágrafo sobre Árvores binárias alfabéticas ótimas (codificação Hu – Tucker)):

No problema de codificação padrão de Huffman, supõe-se que qualquer palavra de código possa corresponder a qualquer símbolo de entrada. Na versão alfabética, a ordem alfabética das entradas e saídas deve ser idêntica. Assim, por exemplo,$A = \left\{a,b,c\right\}$ não foi possível atribuir código $H\left(A,C\right) = \left\{00,1,01\right\}$, mas deve ser atribuído $H\left(A,C\right) =\left\{00,01,1\right\}$ ou $H\left(A,C\right) = \left\{0,10,11\right\}$. Isso também é conhecido como problema de Hu – Tucker, depois de TC Hu e Alan Tucker, os autores do artigo que apresentam a primeira solução linearitmica para esse problema alfabético binário ideal, que tem algumas semelhanças com o algoritmo de Huffman, mas não é uma variação desse algoritmo. Essas árvores binárias alfabéticas ideais são frequentemente usadas como árvores de pesquisa binária.

Minha pergunta é: quais são as aplicações dessas árvores? (árvore binária alfabética)
Tentei pesquisar on-line, mas não consegui encontrar uma resposta satisfatória.
Também li a introdução no artigo de Hu & Tucker sobre o assunto: Árvores ideais para pesquisa em computador e código alfabético de comprimento variável , mas não consegui descobrir exatamente o uso dessa árvore a partir do exemplo deles.

Eu posso entender muito bem a necessidade de um código de prefixo ideal e compacto, induzido por uma árvore ideal (por exemplo, código de Huffman); isso pode ser usado para compactação, mas qual é o uso de árvores binárias alfabéticas?

Deixe-me dar um exemplo do mundo real, que é muito semelhante a algo que escrevi uma vez.

Digamos que você esteja implementando um sistema de catálogo de bibliotecas. Um catálogo de biblioteca é conceitualmente uma coleção de documentos (talvez no formato MARC ). Um usuário deste sistema pode inserir uma consulta, como em qualquer mecanismo de pesquisa, e obter um conjunto de documentos em troca. O usuário gostaria de poder classificar o conjunto de resultados por algum campo (por exemplo, título ou autor) e exibir o conjunto de resultados uma tela por vez.

A classificação é um problema bem compreendido. No entanto, suponha que essa seja uma grande biblioteca e uma pesquisa retorne 100.000 documentos relevantes. Claramente, o usuário não vai examinar todos eles! De fato, o usuário pode apenas observar as duas primeiras telas de resultados (por exemplo, 50 a 100 documentos) e perceber que sua consulta é muito ampla e, portanto, refiná-la ainda mais.

Além disso, acessar a chave de classificação de um documento exige a análise do documento. É verdade que você poderia extrair as possíveis chaves de classificação em um formulário em que não fosse necessário analisar o MARC (ou, pior ainda, SGML / XML), embora isso duplicasse os dados. E, além disso, essas são cordas sobre as quais estamos falando. Eles são de comprimento variável, o que dificulta o gerenciamento de memória e disco.

Então você pode tentar um formato de tamanho fixo. Você pode pegar, digamos, os primeiros K caracteres de cada título para um K predeterminado e armazená-lo em uma matriz no disco, indexada pelo número do documento. Em seguida, você pode primeiro classificar os documentos por esses prefixos de seqüência de caracteres (ou seja, algo como uma classificação de bucket / radix), e qualquer documento que se encaixe no mesmo bucket poderá ser classificado extraindo a chave de classificação "real" dos documentos.

O bom disso é que você não precisa classificar completamente o conjunto de resultados. Como o usuário está folheando o conjunto, você só precisa classificar completamente as primeiras telas e reter informações suficientes sobre o intervalo para classificar as outras, se o usuário decidir percorrer até esse ponto.

Então isso é uma melhoria, mas como você define K? Muitos títulos começam com as letras "The" e usam 32 bits de informação para pouquíssimo poder discriminatório. De fato, você provavelmente ficaria surpreso com o número de periódicos chamados "The International Journal of X", ou similar, e algumas pesquisas provavelmente retornarão muitos documentos com títulos semelhantes.

Uma solução possível é usar um código de preservação de pedidos. Compacte todos os títulos usando esse código e armazene os primeiros 64 bits (ou alguma outra quantia fixa) do título compactado em uma matriz em disco. Isso tem algumas vantagens práticas: partes do título que têm muito pouco poder discriminatório recebem palavras de código muito curtas (para não desperdiçar espaço em detalhes irrelevantes), você pode classificá-las porque preserva a ordem e as chaves são de comprimento fixo (portanto, são fáceis de gerenciar de maneira eficiente).