"Anagram solver" based on statistics rather than a dictionary/table?

Posted by James M. on Stack Overflow See other posts from Stack Overflow or by James M.
Published on 2010-04-16T06:12:45Z Indexed on 2010/04/16 6:23 UTC
Read the original article Hit count: 280

Filed under:

markov

|

ngram

|

optimization

|

algorithm

|

machine-learning

My problem is conceptually similar to solving anagrams, except I can't just use a dictionary lookup. I am trying to find plausible words rather than real words.

I have created an N-gram model (for now, N=2) based on the letters in a bunch of text. Now, given a random sequence of letters, I would like to permute them into the most likely sequence according to the transition probabilities. I thought I would need the Viterbi algorithm when I started this, but as I look deeper, the Viterbi algorithm optimizes a sequence of hidden random variables based on the observed output. I am trying to optimize the output sequence.

Is there a well-known algorithm for this that I can read about? Or am I on the right track with Viterbi and I'm just not seeing how to apply it?

© Stack Overflow or respective owner

Related posts about markov

Using Hidden Markov Model for designing AI mp3 player

as seen on Stack Overflow - Search for 'Stack Overflow'
Hey guys. Im working on an assignment, where I want to design an AI for a mp3 player. The AI must be trained and designed with the use of a HMM method. The mp3 player shall have the functionality of adapting to its user, by analyzing incoming biological sensor data, and from this data the mp3 player… >>> More
Programming With Markov Algorithms.

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello! I Wonder if someone has used Markov Algorithm-based programming system or embedded facility in production or for scientific purpose. I know about 'REFAL' programming language invented a thousand years ago, but it all seems to be dead, so.. Ref: http://en.wikipedia.org/wiki/Markov_algorithm >>> More
R library for discrete Markov chain simulation

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, I am looking for something like the 'msm' package, but for discrete Markov chains. For example, if I had a transition matrix defined as such Pi <- matrix(c(1/3,1/3,1/3, 0,2/3,1/6, 2/3,0,1/2)) for states A,B,C. How can I simulate a Markov chain according to that transition matrix? Thanks… >>> More
using R to estimate finite mixture model with underlying Markov process

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, My apologies if this is more of a statistics question than an R question. I am trying to estimate the following model in R. y_t = mu0 (1 - S_t) + mu1 S_t + e_t e_t ~ N(0, sigma_t^2) sigma_t^2 = sigma_0^2 (1 - S_t) + sigma_1^2 S_t where mu_t = mu0 if S_t = 0, mu_t = mu1 if S_t = 1, and… >>> More
How to generate Markov Chain in C#

as seen on Stack Overflow - Search for 'Stack Overflow'
I want to create this Markov Chain in C#. I need to know if there is any other structure other than adjacency list which can work better in this situation. Also how can I use the existing .Net collection type to implement this. >>> More

Related posts about ngram

Ngram IDF smoothing

as seen on Stack Overflow - Search for 'Stack Overflow'
I am trying to use IDF scores to find interesting phrases in my pretty huge corpus of documents. I basically need something like Amazon's Statistically Improbable Phrases, i.e. phrases that distinguish a document from all the others The problem that I am running into is that some (3,4)-grams in my… >>> More
What is the difference between EdgeNGramTokenizerFactory EdgeNGramFilterFactory in SOLR?

as seen on Stack Overflow - Search for 'Stack Overflow'
What is the difference between these two filters? They seem to have the same effect? Can anyone supply an example of how they are applied to some text? Thanks >>> More
Using Markov models to convert all caps to mixed case and related problems

as seen on Stack Overflow - Search for 'Stack Overflow'
I've been thinking about using Markov techniques to restore missing information to natural language text. Restore mixed case to text in all caps Restore accents / diacritics to languages which should have them but have been converted to plain ASCII Convert rough phonetic transcriptions back into… >>> More
"Anagram solver" based on statistics rather than a dictionary/table?

as seen on Stack Overflow - Search for 'Stack Overflow'
My problem is conceptually similar to solving anagrams, except I can't just use a dictionary lookup. I am trying to find plausible words rather than real words. I have created an N-gram model (for now, N=2) based on the letters in a bunch of text. Now, given a random sequence of letters, I would… >>> More
Simple NLP: How to use ngram to do word similarity?

as seen on Stack Overflow - Search for 'Stack Overflow'
Dear Everyone, I Hear that google uses up to 7-grams for their own data. I am interested in finding words that are similar in context (i.e. cat and dog) and I was wondering how do I compute the similarity of two words on a n-gram model given that n 2. Given a sample set like this forexample: (I… >>> More