我正在为游戏文本扭曲做研究项目，文本将自动从字典中搜索单词并打乱，并使用与此站点http://grecni.com/texttwist 相同的概念处理要自动找到的单词。 php，我还需要提供一个算法，我将用于我的项目，我计划在这个网站http://grecni.com/texttwist.php中包含这个词 unscrambler但我不知道什么算法可能用于在我发布的网站上执行操作。有没有人知道使用什么类型，或者你所说的算法，或者可以使用会给出相同结果的算法，将不胜感激。
问问题
2295 次
3 回答
2
您想要的数据结构称为有向无环字图（dawg）
关于这个问题已经回答了：
您也许还可以实现levenshtein 算法，该算法将完成几乎相同的结果： MySQL - 我应该为此使用哪个哈希算法？
更新：
在给自己一个挑战来创建一个示例来演示我想出的算法之后，因为它来自为我的 cms 构建的插件，它包含在一个类中，但你知道有一个演示 @ http://cherone.co .uk/scrabble_suggest
首先，我创建了一个带有 id、word、sorted 的表（word = 实际单词，sorted = 单词按字母顺序排序，例如：aardvark sorted will be 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
一种方法是生成所有可能的字母排列并将它们与字典进行匹配。对于N字母字符序列，O(N!)如果您将字典保存在集合数据结构中，这将需要时间。
对于较短的序列（大约 10 个字符），这是一个非常好的策略。
对于更长的序列，你应该做相反的事情。您可以遍历字典并确定您的字符序列是否具有组成单词的字符。对于M字典元素，这将花费或多或少的O(M)时间。有多种方法可以加速这种技术，例如预先计算每个字典条目中每个字母的数量。
于 2012-06-22T01:06:16.550 回答
1
编辑：我下面的那位先生对这个主题给出了更严格和更彻底的算法处理，所以我会引导你去他的解释（它采用了我的大 O 符号......令人尴尬地没有）。
实际上，尽管 VanDang 称其为“幼稚方法”，但测试给定的有限字符集的所有可能组合并没有错。只要阻止一个人提供任意数量的字符，就最多有 !n 个字母组合（其中 n = 字母的数量，假设没有重复），并且由于英语单词不得到那么长，测试每个组合不会那么糟糕。
毕竟，穷举法实际上是一种在生成硬件描述时优化大型布尔表达式的公认方法。
于 2012-06-22T01:07:35.817 回答