manera más eficiente de encontrar cadenas parciales en un archivo grande de cadenas (python)

Question

Descargué el archivo de títulos de artículos de Wikipedia que contiene el nombre de cada artículo de Wikipedia. Necesito buscar todos los títulos de los artículos que puedan ser una posible coincidencia. Por ejemplo, podría tener la palabra "hockey", pero el artículo de Wikipedia para hockey que me gustaría es "Ice_hockey". También debería ser una búsqueda insensible a mayúsculas y minúsculas.

Estoy usando Python, ¿hay una forma más eficiente que hacer una búsqueda línea por línea? Voy a realizar esta búsqueda como 500 o 1000 veces por minuto idealmente. Si línea por línea es mi única opción, ¿hay algunas optimizaciones que puedo hacer dentro de esto?

Creo que hay varios millones de líneas en el archivo.

¿Alguna idea?

Gracias.

Answer 1

La respuesta de Greg es buena si quiere hacer coincidir palabras individuales. Si desea hacer coincidir en subcadenas, necesitará algo un poco más complicado, como un árbol de sufijos (http://en.wikipedia.org/wiki/Suffix_tree). Una vez construido, un árbol de sufijos puede responder de manera eficiente a las consultas de subcadenas arbitrarias, por lo que en su ejemplo podría coincidir con "Ice_Hockey" cuando alguien buscaba "corvejón".

Answer 2

Si tiene un conjunto de datos fijo y consultas variables, la técnica habitual es reorganizar el conjunto de datos en algo que pueda buscarse más fácilmente. En un nivel abstracto, puede dividir el título de cada artículo en palabras minúsculas individuales y agregar cada una de ellas a una estructura de datos de diccionario de Python. Luego, cada vez que obtenga una consulta, convierta la palabra de consulta a minúscula y búsquela en el diccionario. Si cada valor de entrada del diccionario es una lista de títulos, entonces puede encontrar fácilmente todos los títulos que coinciden con una palabra de consulta determinada.

Esto funciona para palabras sencillas, pero deberá considerar si desea hacer coincidencias con palabras similares, como encontrar "fumar" cuando la consulta es "humo".

Answer 3

Le sugiero que ponga sus datos en una base de datos sqlite, y use el operador SQL 'like' para sus búsquedas.