algorithm - Cómo dividir una cadena en palabras Ej: "stringintowords"-> "String Into Words"?

nlp dynamic-programming

Question

¿Cuál es la forma correcta de dividir una cadena en palabras? (la cadena no contiene espacios ni signos de puntuación)

Por ejemplo: "stringintowords" -> "String Into Words"

¿Podría indicarnos qué algoritmo debería usarse aquí?

! Actualización: para aquellos que piensan que esta pregunta es solo por curiosidad. Este algoritmo podría usarse para camuflar nombres de dominio ("sportandfishing .com" -> "SportAndFishing .com") y este algoritmo es utilizado actualmente por aboutus dot org para realizar esta conversión dinámicamente.

Answer 1

Como lo mencionaron muchas personas aquí, este es un problema de programación dinámico estándar y sencillo: Falk Hüffner ofrece la mejor solución. Información adicional sin embargo:

(a) debes considerar la implementación de isWord con un trie, lo que te ahorrará mucho tiempo si lo usas correctamente (es decir, probando incrementalmente las palabras).

(b) escribir "programación dinámica de segmentación" arroja una puntuación de respuestas más detalladas, desde conferencias de nivel universitario con algoritmo de pseudocódigo, como esta conferencia en Duke (que incluso llega a proporcionar un enfoque probabilístico simple para tratar con qué hacer cuando tienes palabras que no estarán en ningún diccionario).

Answer 2

Considere la gran cantidad de posibles divisiones para una cadena dada. Si tiene n caracteres en la cadena, hay n-1 lugares posibles para dividir. Por ejemplo, para la cadena cat , puedes dividir antes de la a y puedes dividir antes de la t . Esto resulta en 4 posibles divisiones.

Puede ver este problema como elegir dónde necesita dividir la cadena. También necesita elegir cuántas divisiones habrá. Entonces, hay Sum(i = 0 to n - 1, n - 1 choose i) posibles divisiones. Por el teorema del coeficiente binomial , con xey siendo ambos 1, esto es igual a pow (2, n-1).

De acuerdo, gran parte de este cálculo se basa en subproblemas comunes, por lo que la programación dinámica puede acelerar su algoritmo. Fuera de la cabeza, calcular una boolean matrix M such M[i,j] is true if and only if the substring of your given string from i to j is a word ayudaría bastante. Aún tiene una cantidad exponencial de posibles segmentaciones, pero rápidamente podría eliminar una segmentación si una división temprana no forma una palabra. Una solución sería entonces una secuencia de enteros (i0, j0, i1, j1, ...) con la condición de que j sub k = i sub (k + 1) .

Si su objetivo es URL de camello correctamente, evitaría el problema e iría por algo un poco más directo: obtenga la página de inicio para la URL, elimine los espacios y las mayúsculas del código fuente HTML, y busque su cadena. Si hay una coincidencia, encuentre esa sección en el HTML original y devuélvala. Necesitarás una matriz de NumSpaces que declare la cantidad de espacio en blanco que aparece en la cadena original, así:

Needle:       isashort    
Haystack:     This is a short phrase    
Preprocessed: thisisashortphrase   
NumSpaces   : 000011233333444444 

Y tu respuesta vendría de:

location = prepocessed.Search(Needle)
locationInOriginal = location + NumSpaces[location]
originalLength = Needle.length() + NumSpaces[location + needle.length()] - NumSpaces[location]
Haystack.substring(locationInOriginal, originalLength)

Por supuesto, esto se rompería si madduckets.com no tuviera "Mad Duckets" en algún lugar de la página de inicio. Por desgracia, ese es el precio que paga por evitar un problema exponencial.

Answer 3

Cree una lista de palabras posibles, oriéntala de palabras largas a palabras cortas.

Verifique si cada entrada en la lista está en contra de la primera parte de la cadena. Si es igual, elimine esto y añádalo en su oración con un espacio. Repite esto

Answer 4

Debería haber un poco de literatura académica sobre esto. Las palabras clave que desea buscar son segmentación de palabras . Este documento parece prometedor, por ejemplo.

En general, probablemente querrás aprender sobre los modelos de Markov y el algoritmo de Viterbi . Este último es un algoritmo de programación dinámica que puede permitirle encontrar segmentaciones plausibles para una cadena sin probar exhaustivamente cada posible segmentación. La idea esencial aquí es que si tiene n segmentaciones posibles para los primeros m caracteres y solo desea encontrar la segmentación más probable, no necesita evaluar cada una de ellas en los siguientes caracteres: solo necesita continuar evaluando el más probable.

Answer 5

En realidad, con el diccionario, este problema se puede resolver en O(n) tiempo. Más precisamente en (k + 1) * n en el peor, donde n es el número de caracteres en la cadena k es la longitud de la palabra más larga en el diccionario.

Además, el algoritmo le permite saltear basura.

Aquí está la implementación de trabajo en Common Lisp que he creado hace un tiempo: https://gist.github.com/3381522

Answer 6

Estaba viendo el problema y pensé que tal vez podría compartir cómo lo hice. Es un poco difícil explicar mi algoritmo en palabras, así que tal vez podría compartir mi solución optimizada en pseudocódigo:

string mainword = "stringintowords";
array substrings = get_all_substrings(mainword);

/** this way, one does not check the dictionary to check for word validity 
 *  on every substring; It would only be queried once and for all, 
 *  eliminating multiple travels to the data storage
 */
string query = "select word from dictionary where word in " + substrings;
array validwords = execute(query).getArray();

validwords = validwords.sort(length, desc);

array segments = [];
while(mainword != ""){
    for(x = 0; x < validwords.length; x++){
        if(mainword.startswith(validwords[x])) {
            segments.push(validwords[x]);
            mainword = mainword.remove(v);
            x = 0;
        }
    }

    /**
     * remove the first character if any of valid words do not match, then start again
     * you may need to add the first character to the result if you want to
     */
    mainword = mainword.substring(1);
}

string result = segments.join(" ");

Answer 7

Esto es básicamente una variación de un problema de mochila , entonces lo que necesita es una lista completa de palabras y cualquiera de las soluciones cubiertas en Wiki.

Con un diccionario bastante grande, esta será una operación increíblemente intensiva y de larga duración, y ni siquiera puedes estar seguro de que se resuelva este problema.

Answer 8

Esto se puede hacer realmente (hasta cierto punto) sin diccionario. Básicamente, este es un problema de segmentación de palabras no supervisado. Necesita recopilar una gran lista de nombres de dominio, aplicar un algoritmo de aprendizaje de segmentación no supervisado (por ejemplo, Morfessor ) y aplicar el modelo aprendido para nuevos nombres de dominio. Aunque no estoy seguro de qué tan bien funcionaría (pero sería interesante).

Answer 9

La única forma de dividir esa cadena en palabras es usar un diccionario. Aunque esto probablemente requeriría bastante recursos.

Answer 10

La mejor apuesta sería comparar una subcadena de 0 con un diccionario, y cuando encuentre una coincidencia, extraer esa palabra e iniciar una nueva búsqueda de diccionario a partir de ese punto ... pero va a ser muy propenso a errores, y lo hará tiene problemas con plurales y apóstrofes (fregaderos, fregaderos) y otras partes del discurso.

EDITAR

¿"singleemotion" se convertiría en "emoción individual" o "movimiento de pecado glee"?

Answer 11

Si quiere asegurarse de hacerlo bien, tendrá que usar un enfoque basado en el diccionario y será tremendamente ineficiente. También deberá esperar recibir múltiples resultados de su algoritmo.

Por ejemplo: windowsteamblog (de http://windowsteamblog.com/fame )

• blog team windows
• window steam blog

Answer 12

Una solución Java simple que tiene O (n ^ 2) tiempo de ejecución.

public class Solution {
    // should contain the list of all words, or you can use any other data structure (e.g. a Trie)
    private HashSet<String> dictionary;

    public String parse(String s) {
        return parse(s, new HashMap<String, String>());
    }

    public String parse(String s, HashMap<String, String> map) {
        if (map.containsKey(s)) {
            return map.get(s);
        }
        if (dictionary.contains(s)) {
            return s;
        }
        for (int left = 1; left < s.length(); left++) {
            String leftSub = s.substring(0, left);
            if (!dictionary.contains(leftSub)) {
                continue;
            }
            String rightSub = s.substring(left);
            String rightParsed = parse(rightSub, map);
            if (rightParsed != null) {
                String parsed = leftSub + " " + rightParsed;
                map.put(s, parsed);
                return parsed;
            }
        }
        map.put(s, null);
        return null;
    }
}

Answer 13

Supongamos que tiene una función isWord(w) , que verifica si w es una palabra que usa un diccionario. Por simplicidad, supongamos por ahora que solo quiere saber si para algunas palabras es posible tal división. Esto se puede hacer fácilmente con programación dinámica.

Deje S[1..length(w)] una tabla con entradas booleanas. S[i] es verdadero si la palabra w[1..i] se puede dividir. Luego configure S[1] = isWord(w[1]) y for i=2 a length(w) calcule

S [i] = (isWord [w [1..i] o para cualquier j en {2..i}: S [j-1] y isWord [j..i]).

Esto toma O (longitud (w) ^ 2) tiempo, si las consultas del diccionario son de tiempo constante. Para encontrar realmente la división, simplemente almacene la división ganadora en cada S [i] que se establece en verdadero. Esto también se puede adaptar para enumerar todas las soluciones almacenando todas esas divisiones.