開発日記/2009-04-19

いろいろ -- henoheno†

(関連: BugTrack/502 の末尾が発端, BugTrack2/81, BugTrack2/311, 開発日記/2007-03-18)

autolink.dat の中にある正規表現を多少短くするために generate_trie_regex() を作り直し始めたら、特にソート/再ソート周りの面倒さがあり、一から作り直す事に。処理速度と効果のバランスを取りつつやるというのが辛い。

以下は、文字単位にトライ木を作る関数です。(BSD License, revised) 検討中なだけに不要な部分があります。

// 'ABC' => array('A' => array('B' => array('C' => array('' => array()))))
function generate_single_ctrie($string /*, $direction = CTRIE_DIR_L2R, $limit = NULL*/ )
{
	$root   = array();
	$length = mbstrlen($string);

	$node = & $root;
	for($i = 0; $i < $length; $i++) {
		$char = mb_substr($string, $i, 1);
		$node[$char] = array();
		$node = & $node[$char];
	}
	$node[''] = array();

	return $root;
}

function ctrie_marge_string(& $root, $string)
{
	$tmp  = generate_single_ctrie($string);	// Can't reverse yet

	$node = & $root;
	$trie = & $tmp;
	$key  = key($trie);
	while(isset($node[$key])) {
		// Shift
		$node = & $node[$key];
		$trie = & $trie[$key];
		$key  = key($trie);
	}
	if ($key !== NULL) {
		// Merge the branch
		$node[$key] = & $trie[$key];
	}
}

// Character trie
function generate_ctrie($array, $reverse = FALSE, $sort_flag = SORT_STRING)
{
	// Construct
	$root = array();
	foreach($array as $value) {
		ctrie_marge_string($root, $value);
	}

	// Sort
	if ($sort_flag !== FALSE) {
		ctrie_sort($root, $sort_flag);
	}

	return $root;
}

function ctrie_sort(& $ctrie, $sort_flag)
{
		if (count($ctrie) > 1)  ksort($ctrie, $sort_flag);

		// Recurse
		foreach(array_keys($ctrie) as $key) {
			ctrie_sort($ctrie[$key], $sort_flag);
		}
}

var_dump() すると、このような構造ができているのが解ります。

    ["F"]=>
    array(1) {
      ["r"]=>
      array(1) {
        ["o"]=>
        array(1) {
          ["n"]=>
          array(1) {
            ["t"]=>
            array(1) {
              ["P"]=>
              array(1) {
                ["a"]=>
                array(1) {
                  ["g"]=>
                  array(1) {
                    ["e"]=>
                    array(1) {
                      [""]=>
                      array(0) {
                      }

正規表現の短縮については、以下の見通しは立っています。

'color' + 'colour'

従来: 'colo(?:r|ur)'
目標: 'colou?r'

'foo/0' + 'foo/1' + ... + 'foo/9' + 'foo/-'

従来: 'foo/(?:0|1|2|3|4|5|6|7|8|9|-)'
目標: 'foo/[0-9-]'       (一部の状況でのみ有効)
ひょっとしたら: 'foo/[\d-]'

それ以上の処理は(作るのも、現実的な時間で実行するのも)大変だろうと思いましたので、上記までが現時点の目標です。

total:
today:
yesterday:
now: 1

開発日記/2009-04-19

いろいろ -- henoheno†

最新の16件