igualdad - Función hash para cadenas cortas

frases de igualdad de genero cortas

Question

Deseo enviar nombres de funciones de un sistema embebido 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 solo byte 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 gratis para cuerdas cortas.
2. Simple (ya que no quiero demasiado código en mi sistema integrado).
3. Ajustar un solo byte

Obviamente, no necesita ser seguro por ningún medio, solo colisión libre. 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 podría entonces presentarme la lista de veces en que se ejecutó la función myfunc .

¿Hay alguna función hash conocida que tenga las condiciones anteriores?

Editar:

1. Supongo que usaré mucho menos de 256 nombres de funciones.
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 depuración de los propósitos. (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

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 de hash real probablemente no funcionaría porque solo tienes 256 hashes posibles. pero desea mapear al menos 26 ^ 15 valores posibles (suponiendo nombres de funciones inserciones mayúsculas y minúsculas). Incluso si restringió el número de cadenas posibles (aplicando un formato obligatorio), sería difícil obtener nombres significativos y una función hash válida.

Answer 2

No, no 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 id a cada nombre de función? Entonces solo necesitas una tabla de búsqueda en cada lado del cable.

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

Answer 3

Prueba hashing perfecto mínimo :

El hash perfecto mínimo garantiza que n teclas se correlacionarán con 0..n-1 sin colisiones.

Código C está incluido.

Answer 4

Si tiene una forma de rastrear las funciones dentro de su código (es decir, un archivo de texto generado en tiempo de ejecución) puede simplemente usar 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 5

En este caso, podría usar una enum para identificar funciones. Declarar identificadores de función en algún archivo de encabezado:

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 6

Si el emisor y el receptor comparten el mismo conjunto de nombres de función, pueden crear tablas idénticas a partir de estos. 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: al construir las dos tablas hash "síncronas", el orden de inserción es importante ;-)

Answer 7

Aquí se describe una forma sencilla de implementarlo usted 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 digamos que tenemos un conjunto de caracteres de letras inglesas capitales, entonces la longitud del juego de caracteres es 26, donde A podría 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, llevamos a cabo la misma conversión que hicimos en el caso del formato binario

Answer 8

Puede usar un árbol Huffman para abreviar los nombres de sus funciones de acuerdo con la frecuencia con la 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.