1
$\begingroup$

I have an English dictionary (text file) and the frequency of 2-grams, 3-grams and 4-grams as the beginning of each word. I need to write an algorithm that, with a given word, calculates the possible anagrams (which have to be into the dictionary) based on transitions probability (my assignment requires that I use this method).

I thought to use the Viterbi Algorithm but I don't know if it is the right choise. What do you think about a simulated annealing algorithm? Can you give me any help or advice?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Is it anagram from single word to single word? For example the name Voltaire is a sigle word anagram built from 2 words and one initial. See also: anagramgenius.com/server.html. What are the permissible uses of the dictionnary? $\endgroup$
    – babou
    Jan 8, 2015 at 12:43
  • $\begingroup$ I have to look for anagrams from a single word. The dictionary will be used to decide if the anagrams can be accepted, i have to get the anagrams which are into it. $\endgroup$
    – Zirko88
    Jan 8, 2015 at 18:14

1 Answer 1

Reset to default
1
$\begingroup$

There's a better way to list all anagrams.

Given a word, compute its "canonical form" by sorting the individual letters into alphabetical order. For instance, BASEBALL becomes AABBELLS. Do this for each word in the dictionary, and build a data structure that maps from a canonical form to the list of words with that canonical form (e.g., from AABBELLS to BASEBALL) -- for instance, you might use a hashtable or a sorted list.

Now, given one English word, if you want to find all anagrams of it, you can rapidly compute all anagrams by computing its canonical form and then looking that up in your data structure.

This doesn't require n-grams, transition probabilities, Viterbi algorithm, or anything fancy like that -- just sorting and simple data structures. Thus, it can be coded up quickly and elegantly; and it will be very efficient.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for sharing your solution.. but my teacher asks me to use n-grams and transitions probability :( $\endgroup$
    – Zirko88
    Jan 8, 2015 at 8:44
  • $\begingroup$ This does not seem to work for multiple words anagram, as there is no longer a bound on the number of characters, or strings ... though it could provide prefixes. $\endgroup$
    – babou
    Jan 8, 2015 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.