Algoritmo para buscar palabras clave y frases clave en una cadena

Question

Necesito consejos o instrucciones sobre cómo escribir un algoritmo que encontrará palabras clave o frases clave en una cadena.

La cadena contiene:

• Información técnica escritos en Inglés (GB)
• Palabras formas separado por espacios
• Un palabra clave no contiene un espacio pero puede contener un guión, apóstrofo, dos puntos,
• A frase clave puede contener un espacio, una coma u otro signo de puntuación
• Si aparecen dos o más palabras clave juntas, es probable que se trate de una frase clave, p. "unidad de inversor"
• El texto también contiene HTML, pero esto se puede eliminar de antemano si es necesario
• No palabras clave serían palabras como "y", "el", "nosotros", "ver", "buscar", etc.
• Las palabras clave no distinguen entre mayúsculas y minúsculas, por ej. "Inversor" y "inversor" son la misma palabra clave

El algoritmo tiene los siguientes requisitos:

1. operar en un procesamiento por lotes escenario, por ejemplo, ejecutar una vez o dos veces al día
2. cadenas de procesos que varían en longitud desde aproximadamente 200 a 7000 caracteres
3. Proceso 1000 cadenas en menos de 1 hora
4. ejecutará en un servidor con una buena potencia moderadamente
5. escrito en una de las siguientes: C#, VB.NET, o T-SQL tal vez incluso F #, Python o Lua etc.
6. no ¿se basan en una lista de palabras clave predefinidas o frases clave
7. Pero ¿puede confiar en una lista de exclusiones de palabras clave, p. "y", "el", "ir", etc.
8. Idealmente transferible a otros idiomas, por ejemplo. no se basa en funciones específicas del idioma, p. metaprogramming
9. salida una lista de palabras clave (orden decreciente de frecuencia), seguido de una lista de palabras clave (en orden decreciente de frecuencia)

Sería genial adicional si se podría procesar hasta 8000 caracteres en cuestión de segundos, para que pueda ejecutarse en tiempo real, ¡pero ya estoy pidiendo lo suficiente!

Sólo en busca de consejos y direcciones:

• Si esto se considera como dos algoritmos separados?
• ¿Hay algún algoritmo establecido que pueda seguir?
• ¿Son mis requisitos factibles?

Muchas gracias.

P.S. Las cadenas se recuperarán de una base de datos SQL Server 2008 R2, por lo que idealmente el lenguaje tendría soporte para esto, de lo contrario, debe poder leer/escribir en STDOUT, un conducto, una secuencia o un archivo, etc.

Answer 1

La lógica involucrada hace que sea complicado ser programado en T-SQL. Elija un idioma como C#. Primero intente hacer una aplicación de escritorio simple. Más tarde, si encuentra que cargar todos los registros de esta aplicación es demasiado lento, podría escribir un procedimiento almacenado de C# que se ejecuta en el servidor SQL. Dependiendo de la política de seguridad del servidor SQL, deberá tener una clave sólida.

---

Para el algoritmo ahora. Una lista de palabras excluidas se denomina comúnmente lista de palabras finales. Si busca en Google este término de búsqueda, puede encontrar listas de palabras con las que puede comenzar. Añadir estas palabras vacías a un HashSet<T> (voy a estar usando C# aquí)

HashSet<string> stopWords = new HashSet<string>(StringComparer.OrdinalIgnoreCase); 
string[] lines = File.ReadAllLines("C:\stopwords.txt"); 
foreach (string s in lines) { 
    stopWords.Add(s); // Assuming that each line contains one stop word. 
} 

Más tarde se puede mirar si un candidato de palabra clave se encuentra en la lista de palabras de parada con

If (!stopWords.Contains(candidate)) { 
    // We have a keyword 
} 

HashSets son rápidos. Tienen un tiempo de acceso de O (1), lo que significa que el tiempo requerido para hacer una búsqueda no depende del número de elementos que contiene.

Buscando las palabras clave se puede hacer fácilmente con Regex.

string text = ...; // Load text from DB 
MatchCollection matches = Regex.Matches(text, "[a-z]([:']?[a-z])*", 
             RegexOptions.IgnoreCase); 
foreach (Match match in matches) { 
    if (!stopWords.Contains(match.Value)) { 
     ProcessKeyword(match.Value); // Do whatever you need to do here 
    } 
} 

Si encuentra que a-z es demasiado restrictiva para las cartas y la necesidad letras acentuadas se puede cambiar la expresión de expresiones regulares a @"\p{L}([:']?\p{L})*". La clase de caracteres \p{L} contiene todas las letras y modificadores de letras.

Las frases son más complicadas. Podría tratar de dividir primero el texto en frases y luego aplicar la búsqueda por palabras clave en estas frases en lugar de buscar las palabras clave en todo el texto. Esto le daría la cantidad de palabras clave en una frase al mismo tiempo.

Dividir el texto en frases implica buscar frases que terminen con "." o "?" o "!" o ":". Debe excluir los puntos y dos puntos que aparecen dentro de una palabra.

string[] phrases = Regex.Split(text, @"[\.\?!:](\s|$)"); 

Busca las puntuaciones seguidas de un espacio en blanco o un final de línea. Pero debo aceptar que esto no es perfecto. Podría detectar erróneamente abreviaturas como final de frase. Tendrás que hacer experimentos para refinar el mecanismo de división.