我正在为一个游戏 Text twist 做研究项目，文本会自动从字典中搜索单词然后打乱，并使用与本网站相同的概念自动处理要找到的单词 http://grecni.com/texttwist.php ，我还需要提供一个我将用于我的项目的算法，我打算在这个网站中包含这个词 unscrambler http://grecni.com/texttwist.php但我不知道可能使用什么算法来执行我发布的网站上完成的操作。有谁知道所使用的算法是什么类型，或者您称之为什么，或者可以使用会产生相同结果的算法，将不胜感激该算法的示例。

最佳答案

你想要的数据结构叫做Directed Acyclic Word Graph (dawg)

关于这个已经回答了一些问题:

Algorithm to get a list of all words that are anagrams of all substrings (scrabble)?

Writing an algorithm for scrabble

您也许还可以实现 levenshtein algorithm这将完成几乎相同的结果: MySQL - Which Hash Algo should I use for this?

更新:

在给自己一个挑战来创建一个示例来演示算法之后，我想到了这个，因为它来自为我的 cms 构建的插件，它包装在一个类中，但你明白有一个演示 @ http://cherone.co.uk/scrabble_suggest

首先，我创建了一个包含 id、word、sorted 的表(word = 实际单词，sorted = 按字母顺序排序的单词，例如:aardvark sorted 将是 aaadkrrv)我刚刚在互联网上找到了一个英语单词列表。

表单发布字符串，然后按字母顺序对字符串进行排序以匹配排序列的 1:1，然后将字符串拆分为每个字符，然后按顺序查询直到最后一个字符。感兴趣的函数是 str_sort,permute,swap 也许它有些有趣..

<?php 
/**
 * Scrabble solver Plugin this file is "inline" included within the frontController class
 */
Class plugin{

    function __construct($core) {
        $this->core = $core;
        $this->plugin_path = SITE_ROOT.'/core/plugins/'.$this->core->router->action.'/';
        $this->request = explode('/',$this->core->router->request);
        //Assign Page meta tags ect
        $this->core->template->meta_keywords    = 'Text,Twist,Text Twist,word,letter,scrabble,unscrambler,unscramble,word finder,puzzle,anagram,scrabble,cheat,cheater,help,helper,solve,solver,free,php';
        $this->core->template->meta_description = 'Scrabble and Anagram like word solver tool to help unscramble letters and words and cheat at your favorite word puzzle';
        $this->core->template->page_title       = $this->core->template->site_name." - Scrabble and Anagram like word solver";
        $route = (isset($this->request[2])?$this->request[2]:null);
    }

    function load(){
        set_time_limit(0);
        $data=array('var'=>$this,'result'=>'','word'=>'','word_sort'=>'');

        switch($this->core->router->subaction){
            case "index":
                $string='';
                if($_SERVER['REQUEST_METHOD']=='POST'){
                    $string = substr(preg_replace('/[^a-zA-Z]/s', '', trim(strtolower($_POST['letters']))),0,8);
                    $data['word'] = $string;
                    $string = $this->str_sort($string);
                    $data['word_sort'] = $string;
                }
                $stringLen = strlen($string);

                $result = array();
                for($i=2;$i<=$stringLen;$i++){
                    $seq = substr($data['word_sort'],0,$i);

                    $rounds = explode('|',$this->permute($seq,0,strlen($seq)));
                    $r=$i;
                    foreach($rounds as $round){
                        $result[$r] = $this->get_words($round,strlen($seq));
                        $r++;
                    }
                }

                $data['result'] = $result;

                $this->core->template->content_center = $this->core->template->loadContentView(get_class(),$this->core->router->subaction,$data);
                $this->core->template->content_left   = '';
                $this->core->template->content_right  = '';
                break;

            case "update":
                $this->insert_word_lists();
                header('Location: '.SITE_URL.'/'.$this->core->router->action);
                die;
                break;

            case "api":
                header('Content-Type: application/json');
                echo 'No api for this plugin, perhaps one comming soon. ;p';
                break;

            default:
                header('Location: '.SITE_URL.'/'.$this->core->router->action);
                die;
                break;
        }
    }

    //Query Method to search for sequenced alphabetically sorted words.
    private function get_words($word,$stringLen){
        $chars = str_split($word,1);
        $sql = "SELECT DISTINCT `word` FROM `plugin_scrabble_words` WHERE ";
        foreach($chars as $char){
            $sql .=' `sorted` LIKE "%'.$char.'%" AND';
        }
        $sql = trim($sql,'AND');
        $sql .= ' AND LENGTH(sorted) = '.$stringLen;

        $statement = $this->core->db->prepare($sql);
        $statement->execute();

        $result = $statement->fetchAll(PDO::FETCH_ASSOC);

        return $result;
    }

    //A Model method for updating the database word list.
    private function insert_word_lists(){
        set_time_limit(0);
        $lists = glob($this->plugin_path."wordlists/*.txt");
        foreach ($lists as $list){
            $words = file($list);
            foreach($words as $word){
                $word = strtolower(preg_replace('/[^a-zA-Z]/s', '', $word));
                if($this->sql_check_word($word)===false){
                    $this->sql_put_word($word);
                }
            }
        }
    }

    //A Model method for checking the database specific word.
    private function sql_check_word($word){
        $sql = "SELECT `word` FROM `plugin_scrabble_words` WHERE `word` = :word";
        $statement = $this->core->db->prepare($sql);
        $statement->bindParam(':word', $word, PDO::PARAM_STR);
        $statement->execute();
        $result = $statement->fetchAll(PDO::FETCH_ASSOC);

        if(!empty($result)){
            return true;
        }else{
            return false;
        }
    }

    //A Model method for adding the word to the database.
    private function sql_put_word($word){
        $sql = "INSERT into `plugin_scrabble_words` (word,sorted) VALUES (:word,:sorted)";
        $statement = $this->core->db->prepare($sql);
        $sorted = $this->str_sort($word);
        $statement->bindParam(':word', $word, PDO::PARAM_STR);
        $statement->bindParam(':sorted', $sorted, PDO::PARAM_STR);
        $statement->execute();
    }


    //Sort Method that will sort a sring in alphabetical order
    private function str_sort($string) {
        $tmp = str_split($string);
        sort($tmp);
        return implode('',$tmp);
    }

    //Method to generate and return all permutations of the string with | delimiter.
    private function permute($str,$i,$n) {
        if ($i == $n){
            return $str.'|';
        } else {
            for ($j = $i; $j < $n; $j++) {
                $this->swap($str,$i,$j);
                $this->permute($str, $i+1, $n);
                $this->swap($str,$i,$j);
            }
        }
    }

    //Method to swap the char at pos $i and $j of $str.
    private function swap(&$str,$i,$j) {
        $temp = $str[$i];
        $str[$i] = $str[$j];
        $str[$j] = $temp;
    }
}
?> 

关于php - 为此使用什么算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11148876/