python url trie longest-prefix

python - Partidas de prefijo más largas para URL



trie longest-prefix (4)

Necesito información sobre cualquier paquete de python estándar que pueda usarse para la "coincidencia de prefijo más larga" en las URL. He revisado los dos paquetes estándar http://packages.python.org/PyTrie/#pytrie.StringTrie & ''http://pypi.python.org/pypi/trie/0.1.1'' pero no parecen ser útil para la tarea de coincidencia de prefijo más larga en las URL.

Examine, si mi conjunto tiene estas URL 1> http://www.google.com/mail, 2-> http://www.google.com/document, 3-> http://www.facebook.com , etc.

Ahora, si busco ''http://www.google.com/doc'', debería devolver 2 y buscar ''http: //www.face'' debería devolver 3.

Quería confirmar si hay algún paquete de python estándar que pueda ayudarme a hacer esto o si debería implementar un Trie para la coincidencia de prefijos.

No busco un tipo de solución de expresión regular ya que no es escalable a medida que aumenta el número de URL.

Muchas gracias.

La siguiente función devolverá el índice de la coincidencia más larga. También se puede extraer fácilmente otra información útil.

from os.path import commonprefix as oscp def longest_prefix(s, slist): pfx_idx = ((oscp([s, url]), i) for i, url in enumerate(slist)) len_pfx_idx = map(lambda t: (len(t[0]), t[0], t[1]), pfx_idx) length, pfx, idx = max(len_pfx_idx) return idx slist = [ ''http://www.google.com/mail'', ''http://www.google.com/document'', ''http://www.facebook.com'', ] print(longest_prefix(''http://www.google.com/doc'', slist)) print(longest_prefix(''http://www.face'', slist))

Este ejemplo es bueno para listas de URL pequeñas, pero no escala bien.

def longest_prefix_match(search, urllist): matches = [url for url in urllist if url.startswith(search)] if matches: return max(matches, key=len) else: raise Exception("Not found")

Una implementación usando el módulo trie .

import trie def longest_prefix_match(prefix_trie, search): # There may well be a more elegant way to do this without using # "hidden" method _getnode. try: return list(node.value for node in prefix_trie._getnode(search).walk()) except KeyError: return list() url_list = [ ''http://www.google.com/mail'', ''http://www.google.com/document'', ''http://www.facebook.com'', ] url_trie = trie.Trie() for url in url_list: url_trie[url] = url searches = ("http", "http://www.go", "http://www.fa", "http://fail") for search in searches: print "''%s'' ->" % search, longest_prefix_match(url_trie, search)

Resultado:

''http'' -> [''http://www.facebook.com'', ''http://www.google.com/document'', ''http://www.google.com/mail''] ''http://www.go'' -> [''http://www.google.com/document'', ''http://www.google.com/mail''] ''http://www.fa'' -> [''http://www.facebook.com''] ''http://fail'' -> []

o usando PyTrie que da el mismo resultado pero las listas se ordenan de manera diferente.

from pytrie import StringTrie url_list = [ ''http://www.google.com/mail'', ''http://www.google.com/document'', ''http://www.facebook.com'', ] url_trie = StringTrie() for url in url_list: url_trie[url] = url searches = ("http", "http://www.go", "http://www.fa", "http://fail") for search in searches: print "''%s'' ->" % search, url_trie.values(prefix=search)

Estoy comenzando a pensar que un árbol de raíz / árbol de patricia sería mejor desde el punto de vista del uso de la memoria. Así es como se vería un árbol de raíz:

Mientras que el trie se parece más a:

Comparación de rendimiento

suffixtree vs. pytrie vs. trie vs. datrie vs. startswith -funciones

Preparar

El tiempo registrado es un tiempo mínimo entre 3 repeticiones de 1000 búsquedas. Se incluye un tiempo de construcción de trie y se extiende entre todas las búsquedas. La búsqueda se realiza en colecciones de nombres de host de 1 a 1000000 artículos.

Tres tipos de una cadena de búsqueda:

  • non_existent_key - no hay coincidencia para la cadena
  • rare_key - alrededor de 20 en un millón
  • frequent_key : el número de ocurrencias es comparable al tamaño de la colección

Resultados

Consumo máximo de memoria para un millón de URL:

| function | memory, | ratio | | | GiB | | |-------------+---------+-------| | suffix_tree | 0.853 | 1.0 | | pytrie | 3.383 | 4.0 | | trie | 3.803 | 4.5 | | datrie | 0.194 | 0.2 | | startswith | 0.069 | 0.1 | #+TBLFM: $3=$2/@3$2;%.1f

Para reproducir los resultados, ejecute el código de referencia trie .

  • rare_key / nonexistent_key case

    si el número de urls es menor a 10000, entonces datrie es el más rápido, para N> 10000 - suffixtree es más rápido, startwith es significativamente más lento en promedio.

  • ejes:

    • la escala vertical (tiempo) es ~ 1 segundo (2 ** 20 microsegundos)
    • el eje horizontal muestra el número total de urls en cada caso: N = 1, 10, 100, 1000, 10000, 100000 y 1000000 (un millón).

  • frequent_key

    Hasta N = 100000 datrie es el más rápido (para un millón de URL el tiempo está dominado por el tiempo de construcción).

    La mayor parte del tiempo se toma buscando la coincidencia más larga entre las coincidencias encontradas. Entonces, todas las funciones se comportan de manera similar a lo esperado.

startswith : el rendimiento en el tiempo es independiente del tipo de clave.

trie y pytrie comportan de forma similar.

Rendimiento sin tiempo de construcción

  • datrie - el consumo de memoria más rápido y decente

  • startswith está aún más en desventaja aquí porque otros enfoques no son penalizados por el tiempo que lleva construir un trie.

  • datrie , pytrie , trie - casi O (1) (tiempo constante) para clave rara / inexistente

Ajustar (aproximar) polinomios de funciones conocidas para comparación (la misma escala log / log como en las figuras):

| Fitting polynom | Function | |------------------------------+-------------------| | 0.15 log2(N) + 1.583 | log2(N) | | 0.30 log2(N) + 3.167 | log2(N)*log2(N) | | 0.50 log2(N) + 1.111e-15 | sqrt(N) | | 0.80 log2(N) + 7.943e-16 | N**0.8 | | 1.00 log2(N) + 2.223e-15 | N | | 2.00 log2(N) + 4.446e-15 | N*N |

Si está dispuesto a intercambiar RAM por el tiempo de ejecución, entonces SuffixTree podría ser útil. Tiene buenas propiedades algorítmicas, como permite resolver el problema de subcadena común más largo en un tiempo lineal.

Si siempre busca un prefijo en lugar de una subcadena arbitraria, puede agregar un prefijo único al SubstringDict() :

from SuffixTree import SubstringDict substr_dict = SubstringDict() for url in URLS: # urls must be ascii (valid urls are) assert ''/n'' not in url substr_dict[''/n''+url] = url #NOTE: assume that ''/n'' can''t be in a url def longest_match(url_prefix, _substr_dict=substr_dict): matches = _substr_dict[''/n''+url_prefix] return max(matches, key=len) if matches else ''''

Tal uso de SuffixTree parece SuffixTree ser óptimo, pero es 20-150 veces más rápido (sin el tiempo de construcción de SubstringDict() ) que la solución de @ StephenPaulger [que se basa en .startswith() ] en los datos que he probado y podría ser bueno suficiente.

Para instalar SuffixTree , ejecute:

pip install SuffixTree -f https://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees