根據傳入的單字詞找出相關聯的單字詞

因為程式上的需求.所以需要找出一些.
雖然單字詞位置互調了.但還是一樣的字詞.

先記錄一下原始的實現方法.

<?php
$dict = array();
$string = array("bird", "drib", "ridb", "are", "aer", "rae", "rea");
for($i=0;$i<count($string);$i++) {
	insert_node($string[$i], &$dict);
}
find_relation("bird", &$dict);

function insert_node($word, $dict) {
	$index = word_id($word);
	for($node = $dict[$index]; $node != null; $node = $node['next']) {
		if (strcmp($node['word'], $word) == 0) {
			return;
		}
	}
	$p = array("word" => $word, "next" => $dict[$index]);
	$dict[$index] = $p;
}

function word_id($word) {
	$index = 1;
	for($word_length = strlen($word), $i = 0; $i < $word_length; $i++) {
		$index = $index*(ord($word[$i])-ord('A')+1);
	}
	return $index % 300;
}

function find_relation($current_word, $dict) {
	$temp  = array();
	$index = word_id($current_word);
	for($node = $dict[$index]; $node != null; $node = $node['next']) {
		if (strcmp($current_word, $node['word']) != 0) {
			$temp[] = $node['word'];
		}
	}
	echo "Find: ",$current_word," > Borther: ",implode(" ", $temp),"\n";
}
?>

再改變成一個可重用的東西

<?php
class Final_Relation_Word_Normal {
	const MAX_SIZE = 300;
	
	private $dict;
	
	public function word_id($word) {
		$index = 1;
		for($word_length = strlen($word), $i=0; $i<$word_length; $i++) {
			$index = $index * (ord($word[$i]) - ord('A') + 1);
		}
		return $index % static::MAX_SIZE;
	}
	
	public function insert_node($word) {
		$index = $this->word_id($word);
		
		for($node = $this->dict[$index]; $node != null; $node = $node['next']) {
			if (strcmp($node['word'], $word) == 0) {
				return;
			}
		}
		
		$this->dict[$index] = array('word' => $word, 'next' => $this->dict[$index]);
	}
	
	public function find_relation($word) {
		$temp  = array();
		$index = $this->word_id($word);
		for($node = $this->dict[$index]; $node != null; $node = $node['next']) {
			if (strcmp($word, $node['word']) != 0) {
				$temp[] = $node['word'];
			}
		}
		return $temp;
	}
	
	public function __construct($word_list, $current_word) {
		$this->dict = array();
		
		foreach($word_list as $word) {
			$this->insert_node($word);
		}

		echo "Find: ",$current_word," > Borther: ",implode(" ", $this->find_relation($current_word)),"\n";
	}
}

// 測試
new Final_Relation_Word_Normal(array("bird", "drib", "ridb", "are", "aer", "rae", "rea"), "bird");
?>

同時為了應付大量的查找.
所以用 SPL 裡的東西再改良了一下.

<?php
class Final_Relation_Word {
	const MAX_SIZE = 300;
	
	private $dict;
	
	public function word_id($word) {
		$index = 1;
		for($word_length = strlen($word), $i=0; $i<$word_length; $i++) {
			$index = $index * (ord($word[$i]) - ord('A') + 1);
		}
		return $index % static::MAX_SIZE;
	}
	
	private function insert_node($word) {
		$index = $this->word_id($word);
		$node = isset($this->dict[$index]) === true ? $this->dict[$index] : new SplDoublyLinkedList();

		$node->rewind();
		while($node->valid()) {
			$row = $node->current();
			if (strcmp($row['word'], $word) == 0) {
				return;
			}
			$node->next();
		}
		
		$node->push(array('word' => $word));
		$this->dict[$index] = $node;
	}
	
	private function find_relation($word) {
		$temp  = array();
		$index = $this->word_id($word);
		
		$node = $this->dict[$index];

		$node->rewind();
		while($node->valid()) {
			$row = $node->current();
			if (strcmp($word, $row['word']) != 0) {
				$temp[] = $row['word'];
			}
			$node->next();
		}
		
		return $temp;
	}
	
	public function __construct($word_list, $current_word) {
		$this->dict = new SplFixedArray(static::MAX_SIZE);
		
		foreach($word_list as $word) {
			$this->insert_node($word);
		}
		
		echo "Find: ",$current_word," > Borther: ",implode(" ", $this->find_relation($current_word)),"\n";
	}
}

// 測試
new Final_Relation_Word(array("bird", "drib", "ridb", "are", "aer", "rae", "rea"), "bird");
?>

兩個檔案的速度可以用

time test_normal.php
time test_modified.php

參考:

• http://blog.csdn.net/zzran/article/details/8074036