Download DawgSharp - download do código-fonte DawgSharp

DawgSharp

Outro código-fonte

1.0.0

Baixar

[Pacote NuGet] [Obter licença comercial]

DawgSharp, um dicionário de strings inteligente em C#

DAWG (Directed Acycling Word Graph) é uma estrutura de dados para armazenar e pesquisar grandes listas de palavras e dicionários. Pode ser 40x mais eficiente que a classe .NET Dictionary para determinados tipos de dados.

Por exemplo, meu site hospeda um dicionário de 2 milhões de palavras que ocupava 56 megas em disco e demorava 7 segundos para carregar (ao usar Dictionary e BinarySerializer). Depois de mudar para DAWG, agora são necessários 1,4 mega no disco e 0,3 segundos para carregar.

Como isso é possível? Por que o Dicionário padrão não é tão inteligente quanto o DAWG? O problema é que o DAWG funciona bem com strings de linguagem natural e pode não funcionar tão bem com strings geradas, como chaves de licença (OIN1r4Be2su+UXSeOj0TaQ). Palavras da linguagem humana tendem a ter muitas sequências de letras comuns, por exemplo, -ilidade em habilidade , possibilidade , agilidade , etc., e o algoritmo tira vantagem disso ao encontrar essas sequências e armazená-las apenas uma vez para várias palavras. O DAWG também se mostrou útil na representação de dados de DNA (sequências de genes). A história do DAWG remonta a 1985. Para obter mais informações, pesquise no Google DAWG ou DAFSA (Autômato de Estado Finito Acíclico Determinístico).

DawgSharp é uma implementação do DAWG, uma entre muitas. O que o torna especial?

Ele é escrito em C# puro, compila para MSIL (AnyCPU) e roda em .NET 3.5 e superior.
Não tem dependências.
Ele não introduz limitações de caracteres nas chaves. Algumas implementações concorrentes permitem apenas 26 letras em inglês. Esta implementação lida com quaisquer caracteres Unicode.
O algoritmo de compactação visita cada nó apenas uma vez, o que o torna muito rápido (5 segundos para minha lista de 2 milhões de palavras).
Ele oferece persistência pronta para uso: chame Load/Save para gravar os dados no disco e lê-los novamente.
Possui testes unitários (usando a estrutura de testes do Visual Studio).
Ele recebeu várias horas de sessões de criação de perfil de desempenho, por isso é o mais rápido possível. A próxima etapa para torná-lo mais rápido seria reescrever o código relevante em IL.
É compatível com GC: o Garbage Collector vê apenas 3 grandes matrizes de ints onde um Dicionário armazenaria milhões de strings.

Uso

Neste exemplo simularemos um cenário de uso envolvendo dois programas, um para gerar o dicionário e gravá-lo no disco e outro para carregar esse arquivo e usar o dicionário somente leitura para pesquisas.

Primeiro obtenha o código clonando este repositório ou instalando o pacote NuGet.

Crie e preencha um objeto DawgBuilder :

 var words = new [ ] { " Aaron " , " abacus " , " abashed " } ;

var dawgBuilder = new DawgBuilder < bool > ( ) ; // <bool> is the value type.
                                             // Key type is always string.
foreach ( string key in words )
{
    dawgBuilder . Insert ( key , true ) ;
}

(Como alternativa, faça var dawgBuilder = words.ToDawgBuilder(key => key, _ => true); )

Chame BuildDawg para obter a versão compactada e salve-a no disco:

 Dawg < bool > dawg = dawgBuilder . BuildDawg ( ) ; 
// Computer is working.  Please wait ...

using ( var file = File . Create ( " DAWG.bin " ) ) 
    dawg . SaveTo ( file ) ;

Agora leia o arquivo novamente e verifique se uma palavra específica está no dicionário:

 var dawg = Dawg < bool > . Load ( File . Open ( " DAWG.bin " ) ) ;

if ( dawg [ " chihuahua " ] )
{
    Console . WriteLine ( " Word is found. " ) ;
}

O tipo de valor, <TPayload>

As classes Dawg e DawgBuilder usam um parâmetro de modelo chamado <TPayload> . Pode ser do tipo que você quiser. Só para poder testar se uma palavra está no dicionário, basta um bool. Você também pode torná-lo um int , uma string ou uma classe personalizada. Mas tome cuidado com uma limitação importante. DAWG funciona bem apenas quando o conjunto de valores que o TPayload pode assumir é relativamente pequeno. Quanto menor, melhor. Por exemplo, se você adicionar uma definição para cada palavra, cada entrada será única e seu gráfico se tornará uma árvore (o que pode não ser tão ruim!).

MatchPrefix()

Um outro lado atraente do DAWG é sua capacidade de recuperar com eficiência todas as palavras que começam com uma substring específica:

dawg . MatchPrefix ( " awe " )

A consulta acima retornará um IEnumerable<KeyValuePair> que pode conter chaves como awe, aweful e awesome . A chamada dawg.MatchPrefix("") retornará todos os itens do dicionário.

Se você precisar procurar por sufixo, não há método MatchSuffix. Mas o efeito desejado pode ser alcançado adicionando as chaves invertidas e depois usando MatchPrefix() nas chaves invertidas:

dawgBuilder . Insert ( " ability " . Reverse ( ) , true ) ;
.. .
dawg . MatchPrefix ( " ility " . Reverse ( ) )

ObterPrefixos()

GetPrefixes() retorna todos os itens do dicionário cujas chaves são substrings de uma determinada string. Por exemplo:

dawg . GetPrefixes ( " awesomenesses " )

Pode retornar chaves como awe, awesome, awesomeness e finalmente awesomenesses .

GetLongestCommonPrefixLength()

Um outro recurso interessante é o método int GetLongestCommonPrefixLength(IEnumerable<char> word) . Se word for encontrada no dicionário, ela retornará seu comprimento; caso contrário, retornará o comprimento da palavra mais longa encontrada no dicionário e que também é o início da palavra fornecida. Por exemplo, se prepare estiver no dicionário, mas preempt não estiver, então dawg.GetLongestCommonPrefixLength("preempt") retornará 3, que é o comprimento de "pre".

Segurança de linha

A classe DawgBuilder não é thread-safe e deve ser acessada por apenas um thread em um determinado momento.

A classe Dawg é imutável e, portanto, segura para threads.

MultiDawg

A classe MultiDawg pode armazenar vários valores em uma única chave de string de maneira muito eficiente em termos de memória.

Planos futuros

Mais cenários de uso

A API foi projetada para se adequar a um cenário de uso específico (veja acima) e pode ser estendida para suportar outros cenários, por exemplo, ser capaz de adicionar novas palavras ao dicionário após ele ter sido compactado. Eu simplesmente não precisava disso, então não foi implementado. Você não terá nenhuma exceção. Simplesmente não existe um método Insert na classe Dawg .