¿Existe alguna forma mejor de calcular la frecuencia de todos los símbolos en un archivo?

Bien, entonces, supongo que tengo un archivo de texto (que no necesariamente contiene todos los símbolos posibles) y me gustaría calcular la frecuencia de cada símbolo y, después de calcular la frecuencia, necesito acceder a cada símbolo y su frecuencia desde más frecuente a menos frecuente. Los símbolos no son necesariamente caracteres ASCII, podrían ser secuencias de bytes arbitrarias, aunque con la misma longitud.¿Existe alguna forma mejor de calcular la frecuencia de todos los símbolos en un archivo?

estaba considerando hacer algo como esto (en pseudocódigo):

function add_to_heap (symbol) 
    freq = heap.find(symbol).frequency 
    if (freq.exists? == true) 
     freq++ 
    else 
     symbol.freq = 1 
     heap.insert(symbol) 

MaxBinaryHeap heap 
while somefile != EOF 
    symbol = read_byte(somefile) 
    heap.add_to_heap(symbol) 
heap.sort_by_frequency() 

while heap.root != empty 
    root = heap.extract_root() 
    do_stuff(root)

Me preguntaba: ¿hay una manera mejor, más fácil de calcular y almacenar el número de veces que cada símbolo se produce en un archivo?

Fuente

2011-10-04 rps

Parece que tiene dos opciones, hashmap que le da O (1) recuperación de frecuencia pero ningún resultado ordenado (del más frecuente al menos frecuente) O O (lg n) inserte y busque usando árboles/montón de búsqueda pero dándole un orden (más frecuente a menos frecuente) resultado. –

Un montón binario no es una estructura de datos particularmente buena para esto, ya que encontrar un nodo arbitrario en el montón es bastante caro. Harías mejor con un árbol binario o, como han señalado otros, una tabla hash de algún tipo. –

Siempre puede usar un HashMap isntead del Heap. De esta manera, realizarás operaciones que están en O (1) por cada símbolo encontrado en lugar de O (log n), donde n es la cantidad de elementos actualmente en el montón.

Sin embargo, si el número de símbolos distintos está limitado por un número razonable (1 Byte es ideal, 2 Byte debería estar todavía bien), puede usar una matriz de ese tamaño y tener O (1) pero con un costo constante significativamente menor.

Fuente

2011-10-04 19:09:27

Si usted está buscando un "mejor" solución sobre la base de tiempos de funcionamiento, esto es lo que me gustaría sugerir:

Cuando estás leyendo el archivo, usted debe tener sus símbolos ordenados (o hash) por el valor de los símbolos mismos, no sus frecuencias. Esto le permitirá encontrar rápidamente el símbolo actual en su lista de símbolos ya vistos, en lugar de tener que buscar en toda su lista. También debería tener esa estructura inicial capaz de realizar inserciones rápidas; recomendaría un árbol binario de hash.

Una vez que haya leído todos sus símbolos, debe cambiar su orden de acuerdo con los recuentos de frecuencia. Leería todo en una matriz y luego realizaría una ordenación in situ, pero hay muchas formas equivalentes de hacerlo.

Espero que esto ayude!

Fuente

2011-10-04 19:13:42

¿Existe alguna forma mejor de calcular la frecuencia de todos los símbolos en un archivo?

Respuesta

Cuestiones relacionadas