search - subrayar - palabras repetidas en un texto ejemplo
Encuentre la mayorÃa de las frases repetidas en texto enorme (5)
¿Has considerado usar MapReduce ?
Suponiendo que tenga acceso a una infraestructura adecuada, esto parece ser una buena opción. Necesitará un tokenizador que divida líneas en tokens de varias palabras de hasta 10 palabras. No creo que eso sea un gran problema. El resultado del trabajo MR será token -> frequency pares de token -> frequency , que puede pasar a otro trabajo para ordenarlos en las frecuencias (una opción). Sugeriría leer en Hadoop / MapReduce antes de considerar otras soluciones. También puede usar HBase para almacenar salidas intermedias.
paper original sobre MapReduce de Google.
Tengo enormes datos de texto. Toda mi base de datos es formato de texto en UTF-8
Necesito tener una lista de la frase más repetida en todos mis datos de texto.
Por ejemplo, mi deseo muestra algo como esto:
{
''a'': 423412341,
''this'': 423412341,
''is'': 322472341,
''this is'': 222472341,
''this is a'': 122472341,
''this is a my'': 5235634
}
Procesar y almacenar cada frase toma gran tamaño de base de datos. Por ejemplo, almacenar en MySQL o MongoDB. La pregunta es, ¿hay alguna base de datos o alghorithm más eficiente para encontrar este resultado? Solr, Elasticsearch o etc ...
Creo que tengo un máximo de 10 palabras en cada frase que pueden ser buenas para mí.
Esto se puede simplificar enormemente. No necesitas una base de datos en absoluto. Simplemente almacene el texto completo en un archivo. Luego, escriba un script PHP para abrir y leer el contenido del archivo. Use la función de expresiones regulares de PHP para extraer coincidencias. Mantenga el total en una variable global. Escribe los resultados en otro archivo. Eso es.
Si puede almacenar los datos en Apache Solr , entonces el Manejador de solicitudes Luke podría usarse para encontrar las frases más comunes . Consulta de ejemplo:
http://127.0.0.1:8983/solr/admin/luke?fl=fulltext&numTerms=100
Además, el Componente de términos puede ayudar a encontrar las palabras individuales más comunes . Aquí hay un artículo sobre autoservicio de Solr Stopwords que usa el componente de términos para encontrar las 100 palabras indexadas más comunes y agregarlas al archivo de palabras irrelevantes. Consulta de ejemplo:
http://127.0.0.1:8983/solr/terms?terms.fl=fulltext&terms.limit=100
Sugiero combinar ideas de dos campos, aquí: Streaming Algorithms , y Apriori Algorithm From Market-Basket Analysis .
Comencemos con el problema de encontrar las k palabras sueltas más frecuentes sin cargar todo el corpus en la memoria. Un algoritmo muy simple, Sampling (consulte Cómo encontrar elementos frecuentes en flujos de datos ), puede hacerlo muy fácilmente. Además, es muy fácil de implementar en paralelo (se describe a continuación). Hay una gran cantidad de trabajo en las consultas de top-k, incluidas algunas sobre versiones distribuidas (consulte, por ejemplo, Cálculo de consulta E-Top eficiente en redes distribuidas ).
Ahora al problema de k frases más frecuentes (de posiblemente múltiples frases). Claramente, las frases más frecuentes de longitud l + 1 deben contener las frases más frecuentes de longitud l como prefijo, ya que agregar una palabra a una frase no puede aumentar su popularidad. Por lo tanto, una vez que tenga las k palabras más frecuentes, puede escanear el corpus para solo ellas (que es más rápido) para construir las frases más frecuentes de longitud 2. Con esto, puede construir las frases más frecuentes de longitud 3, y pronto. La condición de detención es cuando una frase de longitud l + 1 no desaloja ninguna frase de longitud l .
Una breve descripción del algoritmo de muestreo
Este es un algoritmo muy simple que, con alta probabilidad, encontrará los mejores artículos k de aquellos que tienen frecuencia al menos f . Opera en dos etapas: la primera encuentra elementos candidatos y la segunda los cuenta.
En la primera etapa, seleccione al azar ~ log (n) / f palabras del corpus (tenga en cuenta que esto es mucho menor que n ). Con alta probabilidad, todas las palabras deseadas aparecen en el conjunto de estas palabras.
En la segunda etapa, mantenga un diccionario de los recuentos de estos elementos candidatos; escanee el corpus y cuente las ocurrencias.
Muestra la parte superior k de los elementos resultantes de la segunda etapa.
Tenga en cuenta que la segunda etapa es muy susceptible de implementación paralela. Si divide el texto en segmentos diferentes y cuenta las ocurrencias en cada segmento, puede combinar fácilmente los diccionarios al final.
tokenize por 1 a 10 palabras e inserte en 10 tablas SQL por longitud de token. Asegúrese de usar el índice hash en la columna con tokens de cadena. A continuación, simplemente llame al SELECT token,COUNT(*) FROM tablename GROUP BY token en cada tabla y descargue los resultados en algún lugar y espere.
EDITAR: eso sería inviable para grandes conjuntos de datos, solo para cada actualización de N-gram el recuento por +1 o insertar una nueva fila en la tabla (en MySQL sería una consulta útil INSERT...ON DUPLICATE KEY UPDATE ). Sin embargo, definitivamente debes usar índices hash.
Después de eso simplemente ordena por número de ocurrencias y combina datos de estas 10 tablas (podrías hacerlo en un solo paso, pero eso pondría más tensión en la memoria).
Tenga cuidado con los métodos heurísticos como sugiere Ami Tavory, si selecciona parámetros incorrectos, puede obtener resultados incorrectos (se puede observar un defecto en el algoritmo de muestreo en algunos términos o frases clásicos, por ejemplo, "habeas corpus"), no se seleccionarán habeas ni corpus como frecuente en sí mismo, pero como una frase de 2 palabras, puede muy bien clasificarse más alto que algunas frases que se obtienen agregando / anteponiendo a la palabra común). Seguramente no hay necesidad de usarlos para tokens de menor longitud, solo los puedes usar cuando los métodos clásicos fallan (toma demasiado tiempo o memoria).