Regexp::Trie を PHP に移植した

こんにちは。ごみばこです。

packagist に公開してあるので composer require regexp-trie:dev-master とでもしたらすぐに使うことができます。

sters/regexp-trie - Packagist

use RegexpTrie\RegexpTrie;

$regexpTrie = RegexpTrie::union([
    'C','C#','C++','Clojure','CoffeeScript','CommonLisp',
    'Java','JavaScript','JScript','J#','JSX',
    'Perl','PHP','PostScript','PowerShell','Python',
]);

var_dump($regexpTrie->toRegexp());
// =>
//     /(?:C(?:(?:\+\+|lojure|o(?:ffeeScript|mmonLisp)|#))?|J(?:ava(?:Script)?|S(?:cript|X)|#)|P(?:erl|HP|o(?:stScript|werShell)|ython))/

これは正規表現において Wikipedia や はてなキーワード のような、多数のキーワードを同時に処理しようとすると、選択が多数になるものができあがり、非常にパフォーマンスが悪いものを、トライ木を使って解決するためのものです。

元ネタはこのあたり。

• 404 Blog Not Found:TRIE-Optimized Regexp
• PerlのRegexp::TrieをRubyに移植した - Islands in the byte stream

このトライ木による正規表現の生成ですが、ご覧のとおり Perl や Ruby ではすでに作られているようで PHP には特に見当たらなかったので Ruby のものから翻訳してみました。（ Perl のソースはちょっと分からないところだらけ過ぎてつらかったので… ）

追）PHP には特に見当たらなかったと思っていたのですが packagist を見たらそれっぽいものがありました。。

s9e/regexp-builder - Packagist

ちゃんと実装を追っていないのですが Regexp::Asemble っぽい挙動をしているような…？