algorithm - una - Algoritmo de separación de palabras

palabras para division silabica

Question

¿Cuál es el algoritmo, aparentemente en uso en páginas de estacionamiento de dominios, que toma un grupo de palabras sin espacio (por ejemplo, "thecarrotofcuriosity") y más o menos lo descompone correctamente en las palabras constitutivas (por ejemplo, "la zanahoria de la curiosidad")?

Answer 1

Imaginé estos sitios y lo hice de forma similar a esto:

1. Obtenga una lista de palabras para su idioma de destino
2. Elimina palabras "inútiles" como "a", "the", ...
3. Examine la lista y verifique cuáles de las palabras son subcadenas del nombre de dominio
4. Tome las palabras más comunes de la lista restante (o las que tienen la calificación más alta de AdSense, ...)

Por supuesto, eso lleva a tonterías para el intercambio experto, pero ¿qué otra cosa esperarías allí?

Answer 2

Me imagino que toman una lista de palabras del diccionario como /usr/share/dict/words en su sistema Unix de variedad común o jardín e intentan encontrar conjuntos de coincidencias de palabras (comenzando desde la izquierda?) Que dan como resultado la mayor cantidad de texto original estar cubierto por un fósforo. Una implementación simple de amplitud-primera búsqueda probablemente funcionaría bien, ya que obviamente no tiene que ejecutarse rápidamente.

Answer 3

(Descargo de responsabilidad: Yo no lo probé, así que tómelo simplemente como alimento para la experimentación. 4 gramos se toman principalmente del cielo azul, solo por mi experiencia que 3 gramos no funcionarán demasiado bien; gramos y más podría funcionar mejor, a pesar de que tendrá que lidiar con una mesa bastante grande). También es simplista en el sentido de que no tiene en cuenta la terminación de la cadena; si funciona de otra manera, probablemente debas pensar en arreglar las terminaciones.

Este algoritmo se ejecutará en un tiempo predecible proporcional a la longitud de la cadena que está intentando dividir.

Entonces, primero: tome muchos textos legibles por humanos. para cada uno de los textos, suponiendo que está en una cadena simple str , ejecute el siguiente algoritmo (notación pseudocode-ish, asume que [] es una indexación similar a hashtable, y que los índices inexistentes devuelven ''0''):

for(i=0;i<length(s)-5;i++) {
  // take 4-character substring starting at position i
  subs2 = substring(str, i, 4); 
  if(has_space(subs2)) {
    subs = substring(str, i, 5);
    delete_space(subs);
    yes_space[subs][position(space, subs2)]++;
  } else {
    subs = subs2;
    no_space[subs]++;
  }
}

Esto te construirá las tablas que te ayudarán a decidir si un 4-g dado necesitaría tener insertado un espacio en él o no.

Luego, tome su cadena para dividirla, denote como xstr , y haga:

for(i=0;i<length(xstr)-5;i++) {
  subs = substring(xstr, i, 4);
  for(j=0;j<4;j++) {
    do_insert_space_here[i+j] -= no_space[subs];
  }
  for(j=0;j<4;j++) {
    do_insert_space_here[i+j] += yes_space[subs][j];
  }
}

Luego puede recorrer la matriz " do_insert_space_here []": si un elemento en una posición determinada es mayor que 0, debe insertar un espacio en esa posición en la cadena original. Si es menor que cero, entonces no deberías.

Por favor, deje caer una nota aquí si lo intenta (o algo de este tipo) y funciona (o no funciona) para usted :-)

Answer 4

Comience con una estructura de datos Trie básica que represente su diccionario. A medida que recorre los caracteres de la cadena, busque en su camino a través del trie con un conjunto de punteros en lugar de un solo puntero: el conjunto está sembrado con la raíz del trie. Para cada letra, todo el conjunto se avanza de inmediato a través del puntero indicado por la letra, y si un elemento establecido no puede avanzar por la letra, se elimina del conjunto. Cuando llegue a un posible final de palabra, agregue una nueva raíz de trie al conjunto (haciendo un seguimiento de la lista de palabras que se ven asociadas con ese elemento de conjunto). Finalmente, una vez que todos los caracteres han sido procesados, regrese una lista arbitraria de palabras que está en la raíz de trie. Si hay más de uno, eso significa que la cadena se puede dividir de múltiples maneras (como "therapistforum" que se puede analizar como ["terapeuta", "foro"] o ["el", "violador", "foro"] ]) y no está definido cuál será el que devolveremos.

O, en un pseudocódigo despertado (Java foreach, tupla indicada con parens, set indicado con llaves, contras usando head :: tail, [] es la lista vacía):

List<String> breakUp(String str, Trie root) {
    Set<(List<String>, Trie)> set = {([], root)};
    for (char c : str) {
        Set<(List<String>, Trie)> newSet = {};
        for (List<String> ls, Trie t : set) {
            Trie tNext = t.follow(c);
            if (tNext != null) {
                newSet.add((ls, tNext));
                if (tNext.isWord()) {
                    newSet.add((t.follow(c).getWord() :: ls, root));
                }
            }
        }
        set = newSet;
     }
     for (List<String> ls, Trie t : set) {
        if (t == root) return ls;
     }
     return null;
 }

Avísame si necesito aclarar algo o si me perdí algo ...