[解決済み] どのようなアルゴリズムが使われているのですか？

質問事項

私はゲームテキストのひねりのための研究プロジェクトをやって、テキストは自動的に辞書から単語を検索し、スクランブル、また、このサイトと同じ概念を使用して自動的に検出されるように単語を処理します。 http://grecni.com/texttwist.php 私はまた、私のプロジェクトに使用するアルゴリズムを提供する必要があり、私はこのウェブサイトにこのワードアンスクランブラを含めることを計画しています。 http://grecni.com/texttwist.php しかし、私はどのようなアルゴリズムがおそらく私が投稿したウェブサイト上で行われたアクションを行うために使用されているのか分からない。誰もがどのようなタイプ、またはあなたが使用するアルゴリズムを呼び出す、または同じ結果を与えることを使用することができます知っていますか、アルゴリズムの例は非常に感謝されるでしょう。

どのように解決するのですか？

欲しいデータ構造というのは 有向非循環ワードグラフ(dawg)

これについては、すでに回答済みの質問があります。

すべての部分文字列のアナグラムであるすべての単語のリストを取得するアルゴリズム（スクラブル）？

スクラブルのアルゴリズムの書き方

を実装することもできるかもしれません。 レベンシュタインアルゴリズム ということで、ほぼ同じ結果を得ることができます。 MySQL - どのハッシュアルゴを使用すればよいですか？

アップデートする

アルゴリズムを実証するための例を作成するために自分自身に課題を与えた後、私はこれを思いついた、それは私のCMSのために構築されたプラグインから、そのクラスでラップされていますが、あなたのアイデアを得るデモがある@。 http://cherone.co.uk/scrabble_suggest

まず、id,word,sortedのテーブルを作りました（word＝実際の単語、sorted＝単語のアルファベット順、例えば、aardvarkは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;
    }
}
?>