"Anagram Solver" استنادًا إلى الإحصائيات بدلاً من القاموس/الجدول؟

Question

تشبه مشكلتي من الناحية النظرية حل الجنان الجنسية ، إلا أنني لا أستطيع فقط استخدام البحث في القاموس. أحاول العثور على كلمات معقولة بدلاً من كلمات حقيقية.

لقد قمت بإنشاء نموذج N-Gram (في الوقت الحالي ، n = 2) استنادًا إلى الحروف في مجموعة من النص. الآن ، بالنظر إلى تسلسل عشوائي من الحروف ، أود أن أتخيلها في التسلسل الأكثر ترجيحًا وفقًا لاحتمالات الانتقال. اعتقدت أنني سأحتاج خوارزمية Viterbi عندما بدأت هذا ، ولكن عندما أبدو أعمق ، تعمل خوارزمية Viterbi على تحسين سلسلة من المتغيرات العشوائية المخفية بناءً على الإخراج المرصود. أحاول تحسين تسلسل الإخراج.

هل هناك خوارزمية معروفة لهذا يمكنني أن أقرأ عنها؟ أو هل أنا على المسار الصحيح مع Viterbi وأنا لا أرى كيفية تطبيقه؟

تحديث

لقد أضفت مكافأة لطلب المزيد من البصيرة حول هذه المشكلة. (تحليل يشرح سبب عدم إمكانية اتباع نهج فعال ، والاستدلال/التقريب الأخرى إلى جانب الصلب المحاكاة ، وما إلى ذلك)

Answer 1

إذا فهمت مشكلتك بشكل صحيح ، فأنت تبحث عن جميع التباديل من الحروف في كلمة واحدة مع أدنى منتج من احتمالات 2 غرام.

إذا كانت كلمتك طويلة جدًا بحيث لا يمكن ببساطة القوة الغاشمة في جميع المجموعات ، فقد وجدت أن خوارزميات التحسين العشوائي تنتج نتائج جيدة في وقت قصير. لقد قمت (بخلفية رياضية) ببعض الأعمال على الخوارزمية "محاكاة الصلب"، والتي أعتقد أنها ستناسب مشكلتك بشكل جيد. ومن السهل تنفيذها.

Answer 2

كتمرين ، كتبت تطبيقًا بسيطًا لسلاسل ماركوف في ماتلاب. في الأساس نموذج احتمالي قائم على الحروف لتوليد الكلمات.

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" من Project 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))

فيما يلي مجموعة من الأمثلة التي تم إنشاؤها من الحروف "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-Gram).

الشيء الجميل في مثل هذا النهج هو أنه لا يقتصر على لغة واحدة ، ويمكن تكييفه مع أي شيء آخر عن طريق تغذية المستندات من لغتك المفضلة.

Answer 3

النظر في مجموعة من الحروف K كما رؤوس في الرسم البياني.

أضف حواف موجهة لتمثيل 2-Grams من كل حرف إلى جميع الآخرين ، مع الأوزان التي تتوافق مع احتمالاتها.

"كلمة" ، إذن ، هو طريق من خلال الرسم البياني (الكامل والموجه).

أنت تبحث عن أفضل "كلمة" (مسار) (مسار) (مسار) يستخدم جميع الأحرف (يزور جميع القمم).

هذا ال مشكلة بائع السفر غير المتماثل. إنه NP-Complete. لا أعتقد أنه سيكون من الأسهل إذا كنت تستخدم n-grams أكبر من n = 2 ، لذلك من غير المحتمل أن تجد خوارزمية فعالة ، ولكن أخبرنا إذا كنت تفعل ذلك

(تم محاكاة الصلب أو شيء من هذا القبيل ربما يكون الطريق للذهاب)

Answer 4

يمكنك أيضا أن تفعل ذلك بشكل عشوائي مع سلسلة ماركوف. بالنسبة للمبتدئين ، تأكد من أن جدول N-Gram الخاص بك يتضمن رمز "بداية الكلمة" ؛ ثم ابحث عن التحولات المتاحة من تلك الحالة ، وقم بتصفيةها بحيث تتضمن فقط الحروف المتاحة من حمام السباحة الخاص بك ، واختر بشكل عشوائي بينها باستخدام الاحتمالات المرجحة. ثم ابحث عن التحولات من التالي الحالة ، والتصفية إلى الرسائل المتاحة التي لا تزال متاحة ، وينتهي عندما لا توجد أحرف في المجمع (أو إذا وصلت إلى حالة لا يمكنك الانتقال منها ، والعودة إلى البداية وحاول مرة أخرى).

قد تجد أنه من المفيد أن يكون هذا أكثر عشوائي من بعض الخيارات المتاحة الأخرى ، وإذا كان كذلك جدا عشوائيًا لديك خيار تدليك الاحتمالات ، أو ببساطة توليد بعض الأرقام ن (قل 100) من الكلمات العشوائية ، وفرزها من خلال "احتمالية" ، ثم الاختيار عشوائيًا من بين الأعلى م (ربما 10) ، مما يمنحك تحكمًا جيدًا نسبيًا في ما إذا كانت الكلمات التي تنشئها من أي حقيبة من الحروف أكثر اتساقًا أو أكثر عشوائية.