Descarga DawgSharp - Descarga del código fuente DawgSharp

DawgSharp

Otro código fuente

1.0.0

Descargar

[Paquete NuGet] [Obtener licencia comercial]

DawgSharp, un inteligente diccionario de cadenas en C#

DAWG (Gráfico de palabras acíclico dirigido) es una estructura de datos para almacenar y buscar grandes listas de palabras y diccionarios. Puede ser 40 veces más eficiente que la clase Dictionary .NET para ciertos tipos de datos.

Como ejemplo, mi sitio web alberga un diccionario de 2 millones de palabras que solía ocupar 56 megas en el disco y tardaba 7 segundos en cargarse (al usar Dictionary y BinarySerializer). Después de cambiar a DAWG, ahora se necesitan 1,4 megas en el disco y 0,3 segundos para cargar.

¿Cómo es esto posible? ¿Por qué el Diccionario estándar no es tan inteligente como el DAWG? La cuestión es que DAWG funciona bien con cadenas de lenguaje natural y es posible que no funcione tan bien con cadenas generadas como claves de licencia (OIN1r4Be2su+UXSeOj0TaQ). Las palabras del lenguaje humano tienden a tener muchas secuencias de letras comunes, por ejemplo , habilidad , posibilidad , agilidad , etc., y el algoritmo aprovecha eso para encontrar esas secuencias y almacenarlas solo una vez para varias palabras. DAWG también ha demostrado ser útil para representar datos de ADN (secuencias de genes). La historia de DAWG se remonta a 1985. Para obtener más información, busque en Google DAWG o DAFSA (Autómata de estado finito acíclico determinista).

DawgSharp es una implementación de DAWG, una de muchas. ¿Qué lo hace especial?

Está escrito en C# puro, se compila en MSIL (AnyCPU) y se ejecuta en .NET 3.5 y superior.
No tiene dependencias.
No introduce limitaciones en los caracteres de las claves. Algunas implementaciones competidoras permiten sólo 26 letras en inglés. Esta implementación maneja cualquier carácter Unicode.
El algoritmo de compactación visita cada nodo sólo una vez, lo que lo hace realmente rápido (5 segundos para mi lista de 2 millones de palabras).
Ofrece persistencia lista para usar: llame a Load/Save para escribir los datos en el disco y volver a leerlos.
Tiene pruebas unitarias (utilizando el marco de pruebas de Visual Studio).
Ha recibido varias horas de trabajo de sesiones de creación de perfiles de rendimiento, por lo que es lo más rápido posible. El siguiente paso para hacerlo más rápido sería reescribir el código relevante en IL.
Es compatible con GC: el recolector de basura solo ve 3 grandes conjuntos de entradas donde un diccionario almacenaría millones de cadenas.

Uso

En este ejemplo, simularemos un escenario de uso que involucra dos programas, uno para generar el diccionario y escribirlo en el disco y el otro para cargar ese archivo y usar el diccionario de solo lectura para realizar búsquedas.

Primero obtenga el código clonando este repositorio o instalando el paquete NuGet.

Cree y complete un 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 ) ;
}

(Alternativamente, haga var dawgBuilder = words.ToDawgBuilder(key => key, _ => true); )

Llame BuildDawg para obtener la versión comprimida y guárdela en el disco:

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

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

Ahora vuelva a leer el archivo y verifique si una palabra en particular está en el diccionario:

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

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

El tipo de valor, <TPayload>

Las clases Dawg y DawgBuilder toman un parámetro de plantilla llamado <TPayload> . Puede ser del tipo que quieras. Sólo para poder comprobar si una palabra está en el diccionario, basta con un bool. También puedes convertirlo en un int o una string o una clase personalizada. Pero tenga cuidado con una limitación importante. DAWG funciona bien sólo cuando el conjunto de valores que puede tomar TPayload es relativamente pequeño. Cuanto más pequeño, mejor. Por ejemplo, si agrega una definición para cada palabra, cada entrada será única y su gráfico se convertirá en un árbol (¡lo cual puede que no sea tan malo!).

Prefijo de coincidencia()

Otro lado atractivo de DAWG es su capacidad para recuperar de manera eficiente todas las palabras que comienzan con una subcadena particular:

dawg . MatchPrefix ( " awe " )

La consulta anterior devolverá un IEnumerable<KeyValuePair> que puede contener claves como awe, aweful y awesome . La llamada dawg.MatchPrefix("") devolverá todos los elementos del diccionario.

Si necesita buscar por sufijo, no existe ningún método MatchSuffix. Pero el efecto deseado se puede lograr agregando las claves invertidas y luego usando MatchPrefix() en las claves invertidas:

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

ObtenerPrefijos()

GetPrefixes() devuelve todos los elementos del diccionario cuyas claves son subcadenas de una cadena determinada. Por ejemplo:

dawg . GetPrefixes ( " awesomenesses " )

Podría devolver claves como asombro, asombro, asombro y finalmente asombro .

ObtenerLongestCommonPrefixLength()

Otra característica interesante es el método int GetLongestCommonPrefixLength(IEnumerable<char> word) . Si se encuentra word en el diccionario, devolverá su longitud; si no, devolverá la longitud de la palabra más larga que se encuentre en el diccionario y que también sea el comienzo de la palabra dada. Por ejemplo, si preparar está en el diccionario pero prevenir no, entonces dawg.GetLongestCommonPrefixLength("preempt") devolverá 3, que es la longitud de "pre".

Seguridad del hilo

La clase DawgBuilder no es segura para subprocesos y solo debe acceder a ella un subproceso en un momento determinado.

La clase Dawg es inmutable y, por tanto, segura para subprocesos.

multidawg

La clase MultiDawg puede almacenar múltiples valores contra una sola clave de cadena de una manera muy eficiente en memoria.

Planes futuros

Más escenarios de uso

La API fue diseñada para adaptarse a un escenario de uso particular (ver arriba) y puede ampliarse para admitir otros escenarios, por ejemplo, poder agregar nuevas palabras al diccionario después de compactarlo. Simplemente no necesitaba esto, por lo que no está implementado. No obtendrás ninguna excepción. Simplemente no existe un método Insert en la clase Dawg .