"Решатель анаграмм" на основе статистики, а не словаря/таблицы?

Ответ 1

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

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

Ответ 2

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

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

A "word", то это путь через (полный, направленный) граф.

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

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

(Имитированное отжиг или что-то вроде этого, вероятно, путь)

Ответ 3

В качестве упражнения я написал простую реализацию Марковских цепей в 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

Нам понадобится текст для обучения модели. Мы используем "The Wonderful Wizard of Oz" из проекта 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

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

%# 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-грамм).

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

Ответ 4

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

На самом деле вам может показаться полезным, чтобы это было более случайным, чем некоторые другие доступные параметры, и если он слишком случайный, у вас есть возможность массировать вероятности или просто генерировать некоторое число n (скажем, 100) случайных слов, сортируя их по их "вероятности", а затем выбирая случайным образом из верхнего m (возможно, 10), что дает вам относительно прекрасный контроль над тем, являются ли слова, которые вы генерируете из любого мешка писем, более последовательными или более случайными.