What is the best way to decrypt words using PHP?

Question

I have a list of words and I want to decrypt words using this list of words in PHP.

It seems to me that PHP does not have a built-in function that does this. So can anyone suggest a good algorithm for this, or at least point me in the right direction?

EDIT: edited to add an example

So basically, I am saying that I have a list of words:

apple banana orange 

Then they give me a bunch of scattered letters.

  pplea nanaba eroang 

Answer 1

Given the dictionary of famous words:

 foreach ($list as $word) { if (count_chars($scrambled_word,1) == count_chars($word,1)) echo "$word\n"; } 

Edit: A simple optimization would be to move count_chars($scrambled_word,1)) outside the loop, since it never changes:

 $letters = count_chars($scrambled_word,1) foreach ($list as $word) { if ($letters == count_chars($word,1)) echo "$word\n"; } 

Answer 2

Warning: I rarely use PHP, so this deals only with a general algorithm that should work in almost any language, and not something specific to PHP.

Presumably, you have a word in which the letters were rearranged, and you want to find which words can be made of these letters.

If this is correct, the general idea is quite simple: take a copy of your list of words and sort the letters in each word in alphabetical order. Put the sorted and unsorted versions of each word next to each other and sort everything by sorted words (but keeping each unsorted word along with its sorted version). You might want to collapse duplicates together so that (for example) instead of {abt: bat} and {abt: tab} you have: {abt: bat, tab}

Then, to combine the scrambled word, sort its letters in alphabetical order. Look for matches in the dictionary (since it is sorted, you can use binary search). When you find a match, the result will be the word (or words) associated with this group of sorted letters. Using the example above, if the scrambled word was "tba", you would sort it to get "abt", and then look at "abt" to get "bat" and "tab".

Edit: As @Moron noted in the comments, sorting and binary search are not really decisive points in and of themselves. The main points are to turn all equivalent inputs into identical keys, and then use some kind of quick key search to find a word for that key.

Sorting letters in each word is one of the easiest ways to turn equivalent entries into identical keys. Sorting a list and performing a binary search is an easy way to quickly find keys.

In both cases, there are many alternatives. I'm not at all sure that the alternatives are likely to improve performance, but they certainly could.

For example, instead of a pure binary search, you might have a second level of index that tells you where the keys starting with “a” were keys starting with “b”, etc. Given that several extremely frequently used letters are near the beginning of the alphabet (for example, "e" and "a"), you might be better off sorting the words so that the letters are relatively unusual ('q', 'z', etc. ) are located at the front of the key, and the most frequently used letters are at the end. This would give that first search, based on an initial character, the greatest discrimination.

On the sort / binary search side, there are probably more alternatives and probably more effective arguments for using something else. Hash tables usually allow you to search in (almost) constant time. Attempts can significantly reduce storage, especially when many words have a common prefix. The only obvious drawback is that the code for one of them probably works more (although the type of the PHP array is based on hash settings, so you can probably use it pretty well).

Answer 3

Can be decrypted in O(log p + n) , where

 p = size of dictionary n = length of word to be unscrambled 

Assume that the constant, c , is the largest number of occurrences of any letter in any word plus 1.
Assume that the constant, k , is the number of letters in the alphabet.
Suppose a constant, j , is the largest number of words that can use the same hash version or sort letters.

Initialization of the space O(p) :
1. Using the dictionary D , create a linked list of sorted words, L , whose size will be no more than p , since each word has one sorted version.
2. Associate another column with L with a numeric hash of integers, which can be in the range [0, c^k-1] . 3. For each word in L , generate its hash with the following function: hash(word) = 0 if word is empty or (c^i + hash(remaining substring of the word))
where i is the index of the alphabet based on the zero value of the first letter.

Algorithm:
1. In O(n) define hash, h , the letter-sorted version of the word in question.
2. In O(log p) find the hash in L
3. In O(n) enter a list of j related words of length n .

Answer 4

Try these

http://www.php.net/manual/en/function.similar-text.php http://www.php.net/manual/en/function.soundex.php http://www.php.net/ manual / en / function.levenshtein.php

Answer 5

A slow option would be to generate all permutations of the letters in the scrambled word, and then examine them using pspell_check () .

If you can, however, use the source text file of the dictionary, the best option is to use a simple regular expression to scan it:

 $dict = file_get_contents("words.txt"); // one word per line $n = strlen($word); if (preg_match('/^[$word]{$n}$/im', $dict, $match)) { print $match[0]; } 

I am sure that PCRE performs search for permutations much faster than PHP and the guessing method.

Answer 6

Use PHP array functions as they can solve this for you.

 $words = array('hello', 'food', 'stuff', 'happy', 'fast'); $scrambled_word = 'oehll'; foreach ($words as $word) { // Same length? if (strlen($scrambled_word) === strlen($word)) { // Convert to an array and match if( ! array_diff(str_split($word), str_split($scrambled_word))) { print "Your word is: $word"; } } } 

Basically, you are looking for something of the same length - then you ask PHP to have all the letters the same.

Answer 7

If you have a really large list of words and you want this unscramble operation to be fast, I would put the list of words in the database. Next, add a field to the word list table, which is the sum of the ascii values ​​for the word, and then add the index of this ascii sum.

Whenever you want to get a list of possible matches, just find the word table for ascii sums that match the sum of the scrambled letters. Keep in mind that you may have several false matches, so you will have to compare all matching words so that they contain only the letters of your scrambled word (but the result set should be quite small).

If you do not want to use a database, you can implement the same basic idea using a file, just sort the list by the sum value to quickly find all matches.

Example Data accepts all lowercase letters (a = 97, b = 98, c = 99, ...) bat => 311, cat => 312, ...

Php function example to calculate the sum for a word

 function asciiSum($word) { $characters = str_split(strtolower($word)); $sum = 0; foreach($characters as $character) { $sum += ord($character); } return $sum; } 

Even faster: add another field to the database that represents the string length, then you can search for words based on the sum of ascii and string length, which will further reduce the number of false matches that you will need to check.