Función hash para cadenas cortas

Question

Deseo enviar nombres de funciones de un sistema incrustado débil a la computadora host para fines de depuración. Como los dos están conectados por RS232, que tiene poco ancho de banda, no deseo enviar el nombre de la función literalmente. Hay unos 15 nombres de función de caracteres largos, y a veces quiero enviar esos nombres a una tasa bastante alta.

La solución en la que pensé fue encontrar una función hash que calificaría esos nombres de funciones con un byte único y solo enviaría este byte. La computadora host escanearía todas las funciones en la fuente, calcularía su hash usando la misma función y luego traduciría el hash a la cadena original.

La función hash debe ser

1. colisión libre para cadenas cortas.
2. Simple (ya que no quiero demasiado código en mi sistema integrado).
3. ajustan a un solo byte

Obviamente, esto no tiene por qué ser seguro por cualquier medio, solamente libre de colisiones. Así que no creo que usar la función hash relacionada con la criptografía valga la pena su complejidad.

Un código de ejemplo:

int myfunc() { 
    sendToHost(hash("myfunc")); 
} 

El anfitrión sería entonces capaz de presentar con la lista de veces que se ejecutó la función myfunc.

¿Existe alguna función hash conocida que cumpla las condiciones anteriores?

Editar:

1. supongo voy a utilizar mucho menos de 256 nombres de función.
2. Puedo usar más de un byte, dos bytes me tienen bastante cubierto.
3. Prefiero usar una función hash en lugar de usar el mismo mapa de función a byte en el cliente y el servidor, porque (1) no tengo implementación de mapa en el cliente, y no estoy seguro de querer poner uno para fines de depuración. (2) Requiere otra herramienta en mi cadena de compilación para inyectar la tabla nombre-función en mi código de sistema incorporado. Hash es mejor en este sentido, incluso si eso significa que tendré una colisión de vez en cuando.

Answer 1

Trate minimal perfect hashing:

mínimas garantías de hash perfectas que n teclas se asignarán a 0..n-1 sin colisiones en absoluto.

El código C está incluido.

Answer 2

Hmm con solo 256 valores posibles, ya que analizará su código fuente para conocer todas las funciones posibles, tal vez la mejor manera de hacerlo sería atribuir un número a cada una de sus funciones ???

Una función hash real probablemente no funcionaría porque solo tiene 256 hashes posibles. pero desea mapear al menos 26^15 valores posibles (suponiendo nombres de función insensibles a mayúsculas y minúsculas). Incluso si restringió el número de cadenas posibles (aplicando algún formato obligatorio), sería difícil obtener nombres válidos y una función hash válida.

Answer 3

No, no lo hay.

No se puede crear un código hash libre de colisiones, o incluso cerca de él, con solo un hash de ocho bits. Si permite cadenas que son más largas que un carácter, tiene más cadenas posibles que posibles códigos hash.

¿Por qué no simplemente extraer los nombres de las funciones y dar un nombre a cada nombre de función? Entonces solo necesitas una tabla de búsqueda en cada lado del cable.

(Como otros han demostrado que puede generar un algoritmo de hash sin colisiones si ya tiene todos los nombres de función, pero luego es más fácil simplemente asignar un número a cada nombre para hacer una tabla de consulta ...)

Answer 4

Puede usar un Huffman tree para abreviar los nombres de sus funciones de acuerdo con la frecuencia en que se utilizan en su programa. La función más común podría abreviarse a 1 bit, menos comunes a 4-5, funciones muy raras a 10-15 bits, etc. Un árbol Huffman no es muy difícil de implementar, pero tendrá que hacer algo con respecto a la alineación de bits.

Answer 5

Si usted tiene una manera de seguir las funciones dentro de su código (es decir, un archivo de texto generado en tiempo de ejecución) sólo puede utilizar las ubicaciones de memoria de cada función. No es exactamente un byte, pero es más pequeño que el nombre completo y se garantiza que es único. Esto tiene el beneficio adicional de una baja sobrecarga. Todo lo que necesitaría para 'decodificar' la dirección es el archivo de texto que asigna direcciones a nombres reales; esto podría enviarse a la ubicación remota o, como mencioné, almacenado en la máquina local.

Answer 6

En este caso, puede usar un enum para identificar funciones. Declarar identificadores de función en algún archivo de cabecera:

typedef enum 
{ 
    FUNC_ID_main, 
    FUNC_ID_myfunc, 
    FUNC_ID_setled, 
    FUNC_ID_soundbuzzer 
} FUNC_ID_t; 

Luego, en funciones:

int myfunc(void) 
{ 
    sendFuncIDToHost(FUNC_ID_myfunc); 
    ... 
} 

Answer 7

Si emisor y el receptor comparten el mismo conjunto de nombres de funciones, que pueden construir tablas hash idénticas a partir de éstos. Puede usar la ruta de acceso para llegar a un elemento hash para comunicar esto. Puede ser {posición inicial + número de saltos} para comunicar esto. Esto tomaría 2 bytes de ancho de banda. Para una tabla de tamaño fijo (Linear Probing), solo se necesita el índice final para abordar una entrada.

NOTA: cuando la construcción de las dos tablas hash "sincrónicas", la orden de inserción es importante ;-)

Answer 8

descrito aquí es una forma sencilla de implementar por sí mismo: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html

Aquí hay un fragmento de la publicación:

Se inspira en la forma en que se decodifican los números binarios y se convierten a formato de número decimal. Cada representación de cadena binaria se asigna de forma exclusiva a un número en formato decimal.

si decir que tenemos un conjunto de caracteres de letras mayúsculas inglesas, entonces la longitud del juego de caracteres es 26 donde A puede representarse por el número 0, B por el número 1, C por el número 2 y así sucesivamente hasta Z por el número 25.Ahora, cada vez que queremos asignar una cadena de este conjunto de caracteres a un número único, realizamos la misma conversión que en el caso del formato binario