algorithm - structures - Hashing una estructura de árbol
tree structures (11)
Cada vez que trabaje con árboles, la recursión debería venir a la mente:
public override int GetHashCode() {
int hash = 5381;
foreach(var node in this.BreadthFirstTraversal()) {
hash = 33 * hash + node.GetHashCode();
}
}
La función hash debe depender del código hash de cada nodo dentro del árbol así como de su posición.
Comprobar. Estamos utilizando explícitamente node.GetHashCode() en el cálculo del código hash del árbol. Además, debido a la naturaleza del algoritmo, la posición de un nodo juega un papel en el último código hash del árbol.
Reordenar los hijos de un nodo debe cambiar claramente el código hash resultante.
Comprobar. Se visitarán en un orden diferente en el recorrido en orden que conduce a un código hash diferente. (Tenga en cuenta que si hay dos niños con el mismo código hash, terminará con el mismo código hash al cambiar el orden de esos niños).
Reflejar cualquier parte del árbol debe cambiar claramente el código hash resultante
Comprobar. Una vez más, los nodos serían visitados en un orden diferente que llevaría a un código hash diferente. (Tenga en cuenta que hay circunstancias en las que la reflexión podría conducir al mismo código hash si cada nodo se refleja en un nodo con el mismo código hash).
Acabo de encontrar un escenario en mi proyecto en el que necesito comparar diferentes objetos de árbol para la igualdad con instancias ya conocidas, y he considerado que algún tipo de algoritmo hash que opere en un árbol arbitrario sería muy útil.
Tomemos por ejemplo el siguiente árbol:
O / / / / O O /|/ | / | / | O O O O / / / / O O
Donde cada O representa un nodo del árbol, es un objeto arbitrario, tiene una función hash asociada. Entonces el problema se reduce a: dado el código hash de los nodos de estructura de árbol, y una estructura conocida, ¿qué es un algoritmo decente para calcular un código hash (relativamente) libre de colisiones para todo el árbol?
Algunas notas sobre las propiedades de la función hash:
- La función hash debe depender del código hash de cada nodo dentro del árbol así como de su posición.
- Reordenar los hijos de un nodo debe cambiar claramente el código hash resultante.
- Reflejar cualquier parte del árbol debe cambiar claramente el código hash resultante
Si ayuda, estoy usando C # 4.0 aquí en mi proyecto, aunque principalmente estoy buscando una solución teórica, por lo que el pseudo-código, una descripción o código en otro lenguaje imperativo estaría bien.
ACTUALIZAR
Bueno, aquí está mi propia solución propuesta. Se ha ayudado mucho por varias de las respuestas aquí.
Cada nodo (subárbol / nodo hoja) tiene la siguiente función hash:
public override int GetHashCode()
{
int hashCode = unchecked((this.Symbol.GetHashCode() * 31 +
this.Value.GetHashCode()));
for (int i = 0; i < this.Children.Count; i++)
hashCode = unchecked(hashCode * 31 + this.Children[i].GetHashCode());
return hashCode;
}
Lo bueno de este método, según lo veo, es que los códigos hash se pueden almacenar en caché y solo se vuelven a calcular cuando cambia el nodo o uno de sus descendientes. (Gracias a vatine y Jason Orendorff por señalar esto).
De todos modos, estaría agradecido si la gente pudiera comentar mi solución sugerida aquí, si hace bien el trabajo, entonces genial, de lo contrario, cualquier mejora posible sería bienvenida.
Creo que podría hacer esto recursivamente: suponga que tiene una función hash h que hashes cadenas de longitud arbitraria (por ejemplo, SHA-1). Ahora, el hash de un árbol es el hash de una cadena que se crea como una concatenación del hash del elemento actual (usted tiene su propia función para eso) y los hash de todos los hijos de ese nodo (de las llamadas recursivas del función).
Para un árbol binario, tendrías:
Hash( h(node->data) || Hash(node->left) || Hash(node->right) )
Es posible que deba verificar cuidadosamente si la geometría del árbol se toma en cuenta correctamente. Creo que con algún esfuerzo podrías derivar un método para el cual encontrar colisiones para tales árboles podría ser tan difícil como encontrar colisiones en la función hash subyacente.
De acuerdo, después de su edición donde ha introducido un requisito de que el resultado hash debe ser diferente para diferentes diseños de árbol, solo tiene la opción de atravesar todo el árbol y escribir su estructura en una única matriz.
Eso se hace así: atraviesas el árbol y vuelcas las operaciones que haces. Para un árbol original que podría ser (para una estructura izquierda-derecha-derecha-hermanos):
[1, child, 2, child, 3, sibling, 4, sibling, 5, parent, parent, //we''re at root again
sibling, 6, child, 7, child, 8, sibling, 9, parent, parent]
A continuación, puede ajustar la lista (es decir, efectivamente, una cadena) de la manera que desee. Como otra opción, incluso puede devolver esta lista como resultado de la función hash, por lo que se convierte en una representación de árbol libre de colisiones.
Pero agregar información precisa sobre toda la estructura no es lo que hacen las funciones hash. La forma propuesta debe calcular la función hash de cada nodo y atravesar todo el árbol. Por lo tanto, puede considerar otras formas de hashing, que se describen a continuación.
Si no quieres atravesar todo el árbol:
Un algoritmo que vino a mi mente de inmediato es así. Elija un número primo grande H (que es mayor que el número máximo de hijos). Para hash un árbol, hash su raíz, elija un número de niño H mod n , donde n es el número de hijos de raíz, y hash recursivamente el subárbol de este niño.
Esta parece ser una mala opción si los árboles difieren solo profundamente cerca de las hojas. Pero al menos debería correr rápido para árboles no muy altos.
Si quieres hash menos elementos pero recorre todo el árbol :
En lugar de hash subárbol, es posible que desee hash en capas. Es decir, hash root primero, que hash uno de los nodos que son sus hijos, luego uno de los hijos de los niños, etc. Así que cubre todo el árbol en lugar de uno de los caminos específicos. Esto hace que el proceso de hash sea más lento, por supuesto.
--- O ------- layer 0, n=1
/ /
/ /
--- O --- O ----- layer 1, n=2
/|/ |
/ | / |
/ | / |
O - O - O O------ layer 2, n=4
/ /
/ /
------ O --- O -- layer 3, n=2
Un nodo de una capa se selecciona con la regla H mod n .
La diferencia entre esta versión y la anterior es que un árbol debe sufrir una transformación bastante ilógica para conservar la función hash.
Debo decir que sus requisitos son algo contra todo el concepto de hashcodes.
La complejidad computacional de la función Hash debe ser muy limitada.
Su complejidad computacional no debe depender linealmente del tamaño del contenedor (el árbol); de lo contrario, rompe totalmente los algoritmos basados en código hash.
Tener en cuenta que la posición como propiedad principal de la función de hash de nodos también va en contra del concepto de árbol, pero se puede lograr, si reemplaza el requisito, que TIENE que depender de la posición.
El principio general que sugeriría es reemplazar los requisitos de MUST con los requisitos de SHOULD. De esta forma, puede encontrar el algoritmo apropiado y eficiente.
Por ejemplo, considere construir una secuencia limitada de tokens de código hash entero, y agregue lo que desea a esta secuencia, en el orden de preferencia.
El orden de los elementos en esta secuencia es importante, afecta el valor calculado.
por ejemplo, para cada nodo que quiera calcular:
- agregar el hashcode del objeto subyacente
- agregue los códigos de los objetos subyacentes de los hermanos más cercanos, si están disponibles. Creo que incluso el único hermano de la izquierda sería suficiente.
- agregue el código hash del objeto subyacente del elemento principal y sus hermanos más cercanos, como el nodo en sí, igual que 2.
Repita esto con los abuelos a una profundidad limitada.
//--------5------- ancestor depth 2 and it''s left sibling; //-------/|------- ; //------4-3------- ancestor depth 1 and it''s left sibling; //-------/|------- ; //------2-1------- this;el hecho de que está agregando el código hash de un objeto subyacente de un hermano directo le da una propiedad posicional a la función de hash.
si esto no es suficiente, agregue los niños: debe agregar a cada niño, solo algunos para dar un código de hash decente.
agregue el primer hijo y es el primer hijo y es el primer hijo ... limite la profundidad a una constante y no calcule nada recursivamente, solo el código hash del objeto subyacente del nodo.
//----- this; //-----/--; //----6---; //---/--; //--7---;
De esta forma, la complejidad es lineal a la profundidad del árbol subyacente, no a la cantidad total de elementos.
Ahora tiene una secuencia de enteros, combínelos con un algoritmo conocido, como sugiere Ely anteriormente.
1,2, ... 7
De esta forma, tendrá una función hash liviana, con una propiedad posicional, que no depende del tamaño total del árbol, e incluso que no dependa de la profundidad del árbol, y no requiera recalcular la función hash de todo el árbol cuando cambie la estructura de árbol.
Apuesto a que estos 7 números darían una distribución de hash casi perfecta.
Escribir su propia función hash casi siempre es un error, porque básicamente necesita un título en matemáticas para hacerlo bien. Las funciones Hash son increíblemente intuitivas y tienen características de colisión altamente impredecibles.
No intente combinar códigos hash directamente para nodos Child; esto ampliará cualquier problema en las funciones hash subyacentes. En su lugar, concatenar los bytes sin formato de cada nodo en orden, y alimentar esto como una secuencia de bytes a una función de hash probados y verdaderos. Todas las funciones hash criptográficas pueden aceptar una secuencia de bytes. Si el árbol es pequeño, puede crear una matriz de bytes y hash en una sola operación.
La propiedad libre de colisiones de esto dependerá de cuán libre de colisiones sea la función hash utilizada para los datos del nodo.
Parece que quieres un sistema en el que el hash de un nodo en particular sea una combinación de hash de nodo hijo, donde el orden importa.
Si planea manipular mucho este árbol, es posible que desee pagar el precio en espacio de almacenar el código hash con cada nodo, para evitar la penalización de recalcular al realizar operaciones en el árbol.
Dado que el orden de los nodos secundarios es importante, un método que podría funcionar aquí sería combinar los datos del nodo y los secundarios utilizando múltiplos de número primo y un módulo de suma un número grande.
Para ir a algo similar al código hash String de Java:
Supongamos que tiene n nodos hijos.
hash(node) = hash(nodedata) +
hash(childnode[0]) * 31^(n-1) +
hash(childnode[1]) * 31^(n-2) +
<...> +
hash(childnode[n])
Algunos detalles más sobre el esquema utilizado anteriormente se pueden encontrar aquí: http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/
La técnica habitual de hash de cualquier secuencia es combinar los valores (o hashes de los mismos) de sus elementos de alguna manera matemática. No creo que un árbol sea diferente a este respecto.
Por ejemplo, aquí está la función hash para tuplas en Python (tomada de Objects / tupleobject.c en la fuente de Python 2.6):
static long
tuplehash(PyTupleObject *v)
{
register long x, y;
register Py_ssize_t len = Py_SIZE(v);
register PyObject **p;
long mult = 1000003L;
x = 0x345678L;
p = v->ob_item;
while (--len >= 0) {
y = PyObject_Hash(*p++);
if (y == -1)
return -1;
x = (x ^ y) * mult;
/* the cast might truncate len; that doesn''t change hash stability */
mult += (long)(82520L + len + len);
}
x += 97531L;
if (x == -1)
x = -2;
return x;
}
Es una combinación relativamente compleja con constantes elegidas experimentalmente para obtener mejores resultados para tuplas de longitudes típicas. Lo que trato de mostrar con este fragmento de código es que el problema es muy complejo y muy heurístico, y la calidad de los resultados probablemente dependa de los aspectos más específicos de sus datos, es decir, el conocimiento del dominio puede ayudarlo a alcanzar mejores resultados. Sin embargo, para obtener buenos resultados, no debe mirar demasiado lejos. Supongo que tomar este algoritmo y combinar todos los nodos del árbol en lugar de todos los elementos de la tupla, además de agregar su posición en el juego, le dará un algoritmo bastante bueno.
Una opción de tomar en cuenta la posición es la posición del nodo en una caminata intrarregional del árbol.
Puedo ver que si tiene un gran conjunto de árboles para comparar, entonces podría usar una función hash para recuperar un conjunto de posibles candidatos, luego haga una comparación directa.
Una subcadena que funcionaría es simplemente usar la sintaxis lisp para poner corchetes alrededor del árbol, escribir el identificador de cada nodo en preorden. Pero esto es computacionalmente equivalente a una comparación de pre-orden del árbol, ¿por qué no hacer eso?
He dado 2 soluciones: una es para comparar los dos árboles cuando terminas (necesario para resolver colisiones) y el otro para calcular el código hash.
COMPARACIÓN DE ÁRBOLES:
La manera más eficiente de comparar será simplemente atravesar recursivamente cada árbol en un orden fijo (el preordenamiento es simple y tan bueno como cualquier otra cosa), comparando el nodo en cada paso.
Por lo tanto, solo crea un patrón Visitor que sucesivamente devuelve el siguiente nodo en preorden para un árbol. es decir, su constructor puede tomar la raíz del árbol.
Luego, solo crea dos entradas del Visitante, que actúan como generadores para el próximo nodo en preorden. es decir, Vistor v1 = nuevo visitante (root1), visitante v2 = nuevo visitante (root2)
Escribe una función de comparación que pueda compararse con otro nodo.
Luego, simplemente visite cada nodo de los árboles, comparando y devolviendo falso si la comparación falla. es decir
Módulo
Function Compare(Node root1, Node root2)
Visitor v1 = new Visitor(root1)
Visitor v2 = new Visitor(root2)
loop
Node n1 = v1.next
Node n2 = v2.next
if (n1 == null) and (n2 == null) then
return true
if (n1 == null) or (n2 == null) then
return false
if n1.compare(n2) != 0 then
return false
end loop
// unreachable
End Function
Módulo final
GENERACIÓN DEL CÓDIGO HASH:
si desea escribir una representación de cadena del árbol, puede usar la sintaxis lisp para un árbol, luego muestree la cadena para generar un código hash más corto.
Módulo
Function TreeToString(Node n1) : String
if node == null
return ""
String s1 = "(" + n1.toString()
for each child of n1
s1 = TreeToString(child)
return s1 + ")"
End Function
El nodo.toString () puede devolver la etiqueta única / código hash / lo que sea para ese nodo. Luego puede hacer una comparación de subcadenas a partir de las cadenas devueltas por la función TreeToString para determinar si los árboles son equivalentes. Para un código hash más corto, simplemente muestree la función TreeToString, es decir, tome cada 5 caracteres.
Módulo final
Si tuviera que hacer esto, probablemente haría algo como lo siguiente:
Para cada nodo hoja, calcule la concatenación de 0 y el hash de los datos del nodo.
Para cada nodo interno, calcule la concatenación de 1 y el hash de cualquier información local (NB: puede no ser aplicable) y el hash de los niños de izquierda a derecha.
Esto conducirá a una cascada en el árbol cada vez que cambie algo, pero PUEDE ser lo suficientemente bajo como para que valga la pena. Si los cambios son relativamente poco frecuentes en comparación con la cantidad de cambios, incluso puede tener sentido recurrir a un hash criptográficamente seguro.
Edit1: También existe la posibilidad de agregar una bandera "hash valid" a cada nodo y simplemente propagar un "falso" en el árbol (o "hash invalid" y propagar "true") en el árbol en un cambio de nodo. De esta forma, es posible evitar un nuevo cálculo completo cuando se necesita el hash de árbol y, posiblemente, evitar cálculos de hash múltiples que no se utilizan, con el riesgo de un tiempo ligeramente menos predecible para obtener un hash cuando sea necesario.
Edit3: El código hash sugerido por Noldorin en la pregunta parece que tendría una posibilidad de colisión, si el resultado de GetHashCode alguna vez puede ser 0. Esencialmente, no hay forma de distinguir un árbol compuesto por un solo nodo, con "símbolo". hash "30 y" valor hash "25 y un árbol de dos nodos, donde la raíz tiene un" símbolo hash "de 0 y un" valor hash "de 30 y el nodo secundario tiene un hash total de 25. Los ejemplos son completamente inventado, no sé qué rangos de hash esperados son, así que solo puedo comentar lo que veo en el código presentado.
Usar 31 como la constante multiplicativa es bueno, en el sentido de que causará cualquier desbordamiento en un límite no-bit, aunque estoy pensando que, con suficientes hijos y posiblemente contenido adversarial en el árbol, la contribución hash de elementos se cortó temprano en MAYO estar dominado por elementos hash posteriores.
Sin embargo, si el hash tiene un rendimiento aceptable en los datos esperados, parece que hará el trabajo. Ciertamente es más rápido que usar un hash criptográfico (como se hace en el código de ejemplo que se detalla a continuación).
Edit2: en cuanto a los algoritmos específicos y la estructura de datos mínima necesaria, algo como el siguiente (Python, la traducción a cualquier otro idioma debería ser relativamente fácil).
#! /usr/bin/env python import Crypto.Hash.SHA class Node: def __init__ (self, parent=None, contents="", children=[]): self.valid = False self.hash = False self.contents = contents self.children = children def append_child (self, child): self.children.append(child) self.invalidate() def invalidate (self): self.valid = False if self.parent: self.parent.invalidate() def gethash (self): if self.valid: return self.hash digester = crypto.hash.SHA.new() digester.update(self.contents) if self.children: for child in self.children: digester.update(child.gethash()) self.hash = "1"+digester.hexdigest() else: self.hash = "0"+digester.hexdigest() return self.hash def setcontents (self): self.valid = False return self.contents
Una simple enumeración (en cualquier orden determinista) junto con una función hash que depende de cuándo se visita el nodo debería funcionar.
int hash(Node root) {
ArrayList<Node> worklist = new ArrayList<Node>();
worklist.add(root);
int h = 0;
int n = 0;
while (!worklist.isEmpty()) {
Node x = worklist.remove(worklist.size() - 1);
worklist.addAll(x.children());
h ^= place_hash(x.hash(), n);
n++;
}
return h;
}
int place_hash(int hash, int place) {
return (Integer.toString(hash) + "_" + Integer.toString(place)).hash();
}
class TreeNode
{
public static QualityAgainstPerformance = 3; // tune this for your needs
public static PositionMarkConstan = 23498735; // just anything
public object TargetObject; // this is a subject of this TreeNode, which has to add it''s hashcode;
IEnumerable<TreeNode> GetChildParticipiants()
{
yield return this;
foreach(var child in Children)
{
yield return child;
foreach(var grandchild in child.GetParticipiants() )
yield return grandchild;
}
IEnumerable<TreeNode> GetParentParticipiants()
{
TreeNode parent = Parent;
do
yield return parent;
while( ( parent = parent.Parent ) != null );
}
public override int GetHashcode()
{
int computed = 0;
var nodesToCombine =
(Parent != null ? Parent : this).GetChildParticipiants()
.Take(QualityAgainstPerformance/2)
.Concat(GetParentParticipiants().Take(QualityAgainstPerformance/2));
foreach(var node in nodesToCombine)
{
if ( node.ReferenceEquals(this) )
computed = AddToMix(computed, PositionMarkConstant );
computed = AddToMix(computed, node.GetPositionInParent());
computed = AddToMix(computed, node.TargetObject.GetHashCode());
}
return computed;
}
}
AddToTheMix es una función que combina los dos hashcodes, por lo que la secuencia importa. No sé lo que es, pero puedes descubrirlo. Un poco de desplazamiento, redondeo, ya sabes ...
La idea es que tenga que analizar algún entorno del nodo, dependiendo de la calidad que desee alcanzar.