«Anagram Solver» на основе статистики, а не словаря / таблицы?

Question

Моя проблема концептуально похожа на решение анаграмм, за исключением случаев, когда я не могу просто использовать словарь. Я пытаюсь найти правдоподобные слова, а не реальные слова.

Я создал N-GRAM Model (пока N = 2) на основе букв в кучке текста. Теперь, учитывая случайную последовательность букв, я хотел бы развернуть их в наиболее вероятную последовательность в соответствии с вероятностью перехода. Я думал, что мне понадобятся Алгоритм Витерби Когда я начал это, но, как я выгляжу глубже, алгоритм Vitterbi оптимизирует последовательность скрытых случайных величин, основанных на наблюдаемом выходе. Я пытаюсь оптимизировать выходную последовательность.

Есть ли известный алгоритм для этого, о котором я могу прочитать? Или я на правильном пути с Витерби, и я просто не вижу, как это применить?

Обновлять

Я добавил щедрость, чтобы просить больше внимания этой проблеме. (Анализ, объясняющий, почему эффективный подход не возможно, другие эвристики / приближения помимо симулированного отжига и т. Д.)

Answer 1

Если я правильно понимаю вашу проблему, вы ищете все перестановки букв в слове для одного с самым низким продуктом 2-грамма вероятностей.

Если ваше слово слишком длинное, чтобы просто грубить все комбинации, я обнаружил, что стохастические алгоритмы оптимизации производят хорошие результаты за короткое время. Я (имеющий математический фон) сделал некоторую работу по алгоритму »Имитация отжига«Что я думаю, хорошо вписывался в вашу проблему. И это довольно легко реализовать.

Answer 2

Как упражнение, я написал простую реализацию цепей Маркова в Matlab. В основном его вероятностная модель на основе буквы для создания слов.

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

Нам понадобится какой-нибудь текст для обучения модели. Мы используем «замечательный волшебник Оз» от проекта Гутенберга.

%# 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

Наконец, мы используем модель для образцов случайных слов или образцов слов из набора букв:

%# 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))

Вот куча примеров, генерируемых из букв «Марковок», наряду с вероятностью логики слова, приведенного моделью:

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

Вы можете увидеть, что, хотя ни один из них не правильные слова, они все еще лучше, чем просто случайная последовательность букв. Очевидно, что используют только предыдущий символ для генерации следующего, недостаточно, все же его можно легко расширить на более сложные случаи (N-грамм).

Приятная вещь о таком подходе состоит в том, что он не ограничен одним языком и может быть адаптирован к любому другому, просто кормить его документы с вашего языка выбора.

Answer 3

Рассмотрим множество букв K как вершин в графике.

Добавьте направленные края для представления 2 граммов из каждой буквы всем остальным, с весами, которые соответствуют их вероятностям.

«Слово», затем, это путь через (полный, направленный) граф.

Вы ищете лучшее (наименее или наиболее взвешенное) «слово» (путь), который использует все буквы (посещает все вершины).

Это Асимметричное путешествие Продажа продавца. Отказ Это NP-полное. Я не думаю, что это будет легче, если вы используете N-граммы больше, чем n = 2, поэтому вы вряд ли найдете эффективный алгоритм, но дайте нам знать, если вы сделаете

(Смоделированный отжиг или что-то вроде это, наверное, путь к работе)

Answer 4

Вы также можете сделать это стохастически с цепью Маркова. Для начала убедитесь, что ваш стол N-GRAM включает в себя символ «начало слова»; Затем найдите доступные переходы из этого состояния и отфиксируйте их, чтобы они включали только доступные буквы из вашего пула и выбирают случайным образом среди них, используя взвешенные вероятности. Затем найдите переходы от следующий Состояние, отфильтровая до еще доступных букв и заканчивается, когда в бассейне нет больше букв (или, если вы достигнете состояния, которое вы не можете перейти, вернитесь к началу и попробуйте снова).

Вы действительно можете найти это полезным, что это более случайные, чем некоторые из других доступных вариантов, и если это слишком случайно у вас есть возможность массировать вероятности или просто создавать некоторое количество N. (Скажем 100) случайных слов, сортируя их по их «вероятности», а затем выбирая случайным образом из первых М. (Возможно 10), что дает вам относительно тонкий контроль над тем, являются ли слова, которые вы генерируете из любой сумки букв, являются более последовательными или более случайными.