ゲームテキストツイストの研究プロジェクトを行っている場合、テキストは辞書から単語を自動的に検索してスクランブルし、このサイトhttp://grecni.com/texttwistと同じ概念を使用して自動的に検出される単語を処理します。 php 、私は自分のプロジェクトに使用するアルゴリズムも提供する必要があります。このWebサイトhttp://grecni.com/texttwist.phpにこの単語unscramblerを含める予定ですが、どのアルゴリズムが使用される可能性があるかわかりません。私が投稿したウェブサイトで行われたアクションを実行します。誰もがどのタイプ、またはあなたが使用するアルゴリズムと呼んでいるものを知っているか、または同じ結果をもたらす使用することができますか、アルゴリズムの例は非常に高く評価されます。
2295 次
3 に答える
2
必要なデータ構造は、有向非巡回ワードグラフ（dawg）と呼ばれます。
これについてはすでに回答済みの質問があります。
すべての部分文字列（スクラブル）のアナグラムであるすべての単語のリストを取得するアルゴリズム？
おそらく、ほぼ同じ結果を達成するレーベンシュタインアルゴリズムを 実装することもできます。MySQL-これにはどのハッシュアルゴリズムを使用する必要がありますか？
アップデート：
アルゴリズムを示すための例を作成することに挑戦した後、これを思い付きます。これは、私のcms用に構築されたプラグインからクラスにラップされているためですが、デモがあります@ http://cherone.co .uk / scrabble_suggest
最初に、id、word、sorted（word =実際の単語、sorted =アルファベット順に並べ替えられた単語など）を使用してテーブルを作成しました。たとえば、aardvarksortedは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;
}
}
?>
于 2012-06-22T01:06:59.917 に答える
1
1つのアプローチは、文字のすべての可能な順列を生成し、それらを辞書と照合することです。N文字シーケンスの場合、辞書を設定されたデータ構造に保持すると、これには時間がかかりますO(N!)。
短いシーケンス（10文字程度）の場合、これは完全に優れた戦略です。
より長いシーケンスの場合は、逆を行う必要があります。辞書をループして、文字シーケンスに単語を作成する文字が含まれているかどうかを判断できます。辞書要素の場合M、これには多少O(M)時間がかかります。各辞書エントリの各文字の数を事前に計算するなど、この手法を高速化するさまざまな方法があります。
于 2012-06-22T01:06:16.550 に答える
1
編集：私の下の紳士は、主題のよりアルゴリズム的に厳密で徹底的な扱いをします、そしてそれで私はあなたに彼の説明にあなたを導くでしょう（それは私の...恥ずかしいことにそうではない大きなO表記を採用しています）。
実際、VanDangはこれを「素朴なアプローチ」と呼んでいますが、与えられた有限の文字セットのすべての可能な組み合わせをテストすることに問題はありません。人が任意の数の文字を提供できない限り、最大！nの文字の組み合わせがあり（繰り返しがないと仮定すると、n =文字の数）、英語の単語はそうではありません。そんなに長くなると、それぞれの組み合わせをテストすることはそれほど悪くはないでしょう。
結局のところ、取り尽くし法は、ハードウェア記述を生成するときに大きなブール式を最適化するために実際に受け入れられている方法です。
于 2012-06-22T01:07:35.817 に答える