“Solucionador de Anagrama” basado en las estadísticas en lugar de un diccionario / tabla?

Question

Mi problema es conceptualmente similar a la resolución de anagramas, excepto que no puedo acaba de utilizar una búsqueda de diccionario. Estoy tratando de encontrar las palabras plausibles en lugar de palabras reales.

I han creado un modelo de N-gramo (por ahora, N = 2) en base a las cartas en un montón de texto. Ahora bien, dada una secuencia aleatoria de letras, me gustaría permutar ellos en la secuencia más probable de acuerdo con las probabilidades de transición. Pensé que iba a necesitar la algoritmo de Viterbi cuando empecé esto, pero al mirar más profundo, el Viterbi algoritmo optimiza una secuencia de variables aleatorias búsqueda basado en la salida observada. Estoy tratando de optimizar la secuencia de salida.

¿Existe un algoritmo conocido para esto que puedo leer? O estoy en el camino correcto con Viterbi y yo no estoy viendo cómo se aplica?

Actualizar

He añadido una recompensa para pedir más penetración en este problema. (Análisis explicar por qué un enfoque eficiente no es posible, otras heurísticas / aproximaciones, además de recocido simulado, etc.)

Answer 1

Si entiendo correctamente su problema, que está buscando todas las permutaciones de letras en una palabra de la que tiene el producto más bajo de probabilidades 2 gramos.

Si su palabra es muy larga a la fuerza bruta simplemente todas las combinaciones, he encontrado que los algoritmos de optimización estocásticos producen buenos resultados en un corto tiempo. Yo (que tiene una base matemática) he hecho algunos trabajos en el algoritmo " recocido simulado ", el cual Creo que encajaría muy bien a su problema. Y es bastante fácil de implementar.

Answer 2

A modo de ejercicio, me escribió una implementación sencilla de cadenas de Markov en MATLAB. Básicamente es un modelo probabilístico basado en la carta a las palabras generadoras.

function mc = MC(numStates)
    N = numStates;
    PI = ones(1,N)/N;
    TR = ones(N,N)/N;
    mc = struct('logprob',@logprob, 'train',@train, ...
                'sample',@sample, 'sampleFiltered',@sampleFiltered);

    function train(seqs)
        PI = 1 + histc(cellfun(@(c)c(1), seqs)', 1:N); %#'
        TR = ones(N,N);
        for i=1:numel(seqs)
            ind = sub2ind([N N], seqs{i}(1:end-1), seqs{i}(2:end));
            TR = TR + reshape(histc(ind,1:N*N), [N N]);
        end
        PI = bsxfun(@rdivide, PI, sum(PI,2)+(sum(PI,2)==0));
        TR = bsxfun(@rdivide, TR, sum(TR,2)+(sum(TR,2)==0));
    end

    function seq = sample(len)
        seq = zeros(1,len);
        seq(1) = randsample(1:N, 1, true, PI);
        for t=2:len
            seq(t) = randsample(1:N, 1, true, TR(seq(t-1),:));
        end
    end

    function seq = sampleFiltered(allowed)
        len = numel(allowed);
        seq = zeros(1,len);
        seq(1) = randsample(allowed, 1, true, PI(allowed));
        allowed( find(allowed==seq(1),1,'first') ) = [];
        for t=2:len-1
            seq(t) = randsample(allowed, 1, true, TR(seq(t-1),allowed));
            allowed( find(allowed==seq(t),1,'first') ) = [];
        end
        seq(t) = allowed;
        seq = seq(seq~=0);
    end

    function LL = logprob(seq)
        LL = log(PI(seq(1))) + ...
             sum( log(TR(sub2ind([N N],seq(1:end-1),seq(2:end)))) );
    end
end

Vamos a necesitar algo de texto para entrenar el modelo. Utilizamos 'El maravilloso mago de Oz' en el Proyecto Gutenberg.

%# read the text document
str = lower( urlread('http://www.gutenberg.org/files/55/55.txt') );
SP = char(32);                        %# delimiter (space)
str( ~isstrprop(str, 'alpha') ) = SP; %# replace non-letters with spaces
str( findstr(str, [SP SP]) ) = [];    %# consecutive spaces as one
idx = ( str == SP );                  %# location of spaces
df = diff([1 idx 1]);
len = find(df > 0) - find(df < 0);    %# length of each word
[seqs gn] = grp2idx( str(~idx)' );    %#' map letters to numbers starting from 1
seqs = mat2cell(seqs', 1, len)';      %# put each word in a separate cell
N = length(gn);                       %# A to Z

Por último, se utiliza el modelo para una de las palabras al azar de muestras o palabras de la muestra a partir de un conjunto de letras:

%# train Markov chain
mc = MC(N);
mc.train(seqs);

%# sample a random word
seq = mc.sample( randi([3 10]) );
fprintf('word = %s , logP(word)=%f\n', [gn{seq}], mc.logprob(seq))

%# sample a word from a set of letters
letters = lower('markovchains');
lettersIdx = cellfun(@(c) find(strcmp(c,gn)), cellstr(letters'));   %#'
seq = mc.sampleFiltered(lettersIdx);
fprintf('word = %s , logP(word)=%f\n', [gn{seq}], mc.logprob(seq))

Aquí hay un montón de ejemplos generados a partir de 'markovchains' a las letras, junto con log-probabilidad de la palabra dada el modelo:

word = mivorancask , logP(word)=-29.610819
word = arknoamshiv , logP(word)=-32.496090
word = ancoramshik , logP(word)=-29.299897
word = orchisankav , logP(word)=-29.987204
word = avinchasorm , logP(word)=-27.178507
word = aronchaskim , logP(word)=-25.651964

Se puede ver que, aunque ninguno son palabras correctas, siguen siendo mejor que sólo una secuencia aleatoria de letras. Obviamente utilizando sólo el carácter anterior para generar el siguiente no es suficiente, todavía se puede extender fácilmente a los casos más sofisticados (N-gramo).

Lo bueno de este enfoque es que no es restringido a un solo idioma, y ??puede ser adaptado a cualquier otra simplemente alimentándola documentos desde su idioma de su elección.

Answer 3

Considere el conjunto de letras K como vértices en un gráfico.

Agregar bordes dirigidos a representar los 2-gramos de cada carta a todos los otros, con los pesos que corresponden a sus probabilidades.

A "palabra", entonces, es una ruta a través del gráfico (completo, dirigida).

Se busca la mejor (o menos: más-ponderada) "palabra" (ruta) que utiliza todas las letras (visitas todos los vértices).

Este es el asimétrica Traveling Salesman Problema . Es NP-completo. No creo que va a ser más fácil si se utiliza n-gramas más grande que N = 2, por lo que no es probable encontrar un algoritmo eficiente, pero háganos saber si lo hace

(recocido simulado o algo parecido es probablemente el camino a seguir)

Answer 4

También puede hacerlo de forma estocástica con una cadena de Markov. Para empezar, asegúrese de que la tabla N-gramo incluye un símbolo "principio de la palabra"; luego encontrar las transiciones disponibles a partir de ese estado, y filtrarlos para que sólo se incluyen las cartas disponibles a partir de su piscina, y selecciona al azar entre ellos el uso de probabilidades ponderadas. A continuación, busque las transiciones de la siguiente estado, filtrando a las letras todavía disponibles, y al final, cuando ya no hay más cartas en la piscina (o, si se llega a un estado que no se puede transición de, volver al principio y vuelve a intentarlo).

En realidad se puede encontrar útil que esto es más al azar que algunas de las otras opciones disponibles, y si es también al azar tiene la opción de dar masajes las probabilidades, o simplemente la generación de un número n (digamos 100) de palabras al azar, clasificación ellos por su "probabilidad", y luego elegir al azar entre la parte superior m (quizás 10), que le da un control relativamente fino sobre si las palabras que generan desde cualquier bolsa de cartas son más consistentes o más al azar.