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

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

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

Тогда "слово" - это путь через (полный, направленный) граф.

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

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

(Simulated Annealing или что-то похожее на него, вероятно, будет правильным решением)

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

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

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

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

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

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