Estructura de datos DAWG

Un Directed Acyclic Word Graph (estructura de datos DAWG, por sus siglas en inglés), también llamado Deterministic Acyclic Finite State Automation (DAFSA), es un tipo de estructura de datos que permite representar datos de tipo texto y realizar consultas.

Lo que se genera en las consultas es un grafo en el que se distinguen:

• Nodos: un carácter o símbolo.
• Vértices: enlace con el siguiente carácter o símbolo más probable.

DAWG nos permite definir unos grafos para hacer búsquedas dentro de los mismos. Veamos un ejemplo de la estructura de datos DAWG para entender mejor cómo funciona.

Estructura de datos DAWG

#Estructura de datos DAWG
! wget https://transfer.sh/KWNxRn/datasets.zip
! wget https://transfer.sh/XoRKUW/utils.py

! unzip datasets.zip

from utils import load_movie_titles

#Estructura de datos DAWG
datasets_path = './datasets'
movie_titles_file = 'films.txt'

movies_titles = load_movie_titles (datasets_path, movie_titles_file)

movies_titles

Una vez descargado todo el dataset de las películas que tenemos, vamos a empezar:

from pydawg import DAWG

#Estructura de datos DAWG
dawg = DAWG ()

for w in sorted (m.title for m in movies_titles):
      dawg.add_word_unchecked (w)

import random

Escogemos una película al azar:

t = random.choice (movies_titles).title
t

‘Milla 22’

t in dawg

True

Operaciones DAWG

Búsqueda por prefijo

Ahora buscaremos las películas que contengan la palabra «Batman»:

#Estructura de datos DAWG
for m in dawg.find_all ('Batman'):
      print (m)

Prefijo más largo

#Estructura de datos DAWG
s = 'La guerra de nunca jamás'
pfx = dawg.longest_prefix (s)
print (s [:pfx])

Búsqueda en una oración

Ahora buscaremos cuál es la película que coincide más con la oración «Dónde echan Batman y Robin esta noche»:

#Estructura de datos DAWG
def token_match (dawg, tknlist):
       for n in range (len (tknlist), 0, -1):
             test_str = '  '.join (tknlist [:n])
             if test_str in dawg:
                 return test_str

def token_match_all (dawg, utterance):
       tknlist = utterance.split ()
       return [token_match (dawg, tknlist [chunk:])
                   for chunk in range (len (tknlist))]

token_match_all (dawg, 'Donde echan Batman y Robin esta noche')

[None, None, ‘Batman y Robin’, None, None, None, None]

Y el resultado es Batman y Robin.

Minimal perfect hash

Aquí vemos cuál es el índice del grafo que ocupa la palabra:

dawg.word2index ('Batman')

175

¿Quieres seguir avanzando?

Para poder acceder a las opciones laborales del Big Data, una de las áreas con mejores salarios y una gran demanda, tenemos para ti el Big Data, Inteligencia Artificial & Machine Learning Full Stack Bootcamp. Con esta formación intensiva e íntegra, en muy pocos meses adquirirás los conocimientos teóricos y prácticos imprescindibles para abrirte paso en el mundillo IT. ¡Da el paso definitivo para transformar tu futuro y accede ahora para pedir más información!