Como no pude subir ni el sabado ni domingo por problemas ya que fui a un mandado donde no existen las maquinas y pues no pude pero quieria subir esto aunque no cuente pero cuando busque automatas finitos encontre esta dos cosas que no les entendi mucho:
Un trie es un caso especial de autómata finito determinista (S, Σ, T, s, A), que sirve para almacenar un conjunto de cadenas E en el que:
Σ es el alfabeto sobre el que están definidas las cadenas;
S, el conjunto de estados, cada uno de los cuales representa un prefijo de E;
la función de transición: ; está definida como sigue: T(x,σ) = xσ si , e indefinida en otro caso;
el estado inicial s corresponde a la cadena vacía λ;
el conjunto de estados de aceptación es igual a E.
Su nombre procede del término inglés retrieva.
Σ es el alfabeto sobre el que están definidas las cadenas;
S, el conjunto de estados, cada uno de los cuales representa un prefijo de E;
la función de transición: ; está definida como sigue: T(x,σ) = xσ si , e indefinida en otro caso;
el estado inicial s corresponde a la cadena vacía λ;
el conjunto de estados de aceptación es igual a E.
Su nombre procede del término inglés retrieva.
y
Como sustitución de una Tabla hash
Un Trie puede usarse para reemplazar una Tabla hash, sobre la que presenta las siguientes ventajas:
el tiempo de búsqueda en una Tabla hash imperfecta es del orden de O(n), mientras que en un trie es del orden de O(l). Esto es debido a las colisiones de claves.
en un trie no se producen colisions de claves
no hay que definir una función de hash, o modificarla si añadimos más claves
los contenedores que almacenan distintos valores asociados a una única clave sólo son necesarios si tenemos más de un valor asociada a una única clave. En una tabla hash siempre se necesitan estos contenedores para las colisiones de clave
un trie puede proporcionarnos un ordenamiento alfabético de las entradas por clave
Las principales desventajas de los tries respecto a las tablas hash son:
en determinados casos pueden ser más lentos que las tablas hash en la búsqueda de datos, especialmente si los datos son consultados desde dispositivos de almacenamiento secundario, como disco duro, donde el tiempo de acceso es elevado con respecto a memoria principal
no es sencillo representar todas las claves como cadenas, como los números reales, que pueden tener distintas representaciones en forma de cadena para un mismo número, p.ej. 1, 1.00, 1.000, +1.000,...
a menudo los tries son más ineficientes respecto al espacio que las tablas hash
los tries no suelen estar disponibles con las herramientas de desarrollo software, todo lo contrario que las tablas hash .
Un Trie puede usarse para reemplazar una Tabla hash, sobre la que presenta las siguientes ventajas:
el tiempo de búsqueda en una Tabla hash imperfecta es del orden de O(n), mientras que en un trie es del orden de O(l). Esto es debido a las colisiones de claves.
en un trie no se producen colisions de claves
no hay que definir una función de hash, o modificarla si añadimos más claves
los contenedores que almacenan distintos valores asociados a una única clave sólo son necesarios si tenemos más de un valor asociada a una única clave. En una tabla hash siempre se necesitan estos contenedores para las colisiones de clave
un trie puede proporcionarnos un ordenamiento alfabético de las entradas por clave
Las principales desventajas de los tries respecto a las tablas hash son:
en determinados casos pueden ser más lentos que las tablas hash en la búsqueda de datos, especialmente si los datos son consultados desde dispositivos de almacenamiento secundario, como disco duro, donde el tiempo de acceso es elevado con respecto a memoria principal
no es sencillo representar todas las claves como cadenas, como los números reales, que pueden tener distintas representaciones en forma de cadena para un mismo número, p.ej. 1, 1.00, 1.000, +1.000,...
a menudo los tries son más ineficientes respecto al espacio que las tablas hash
los tries no suelen estar disponibles con las herramientas de desarrollo software, todo lo contrario que las tablas hash .
Estos dos conceptos: trie y tabla hash, alguna explicacion mas entendible, se los agradecederia...
Adios...
No hay comentarios:
Publicar un comentario