運営者情報

運営してるひと: @sters9

       

妻と猫と横浜あたりに住んでいる。最近は Go や Kubernetes や GCP をしています。 PHP や JavaScript もすこし。

プライバシーポリシー

tools.gomiba.co

アーカイブ

2021/02 (12) 2021/01 (8)

2020/05 (2) 2020/04 (2) 2020/02 (2) 2020/01 (1)

2019/12 (3) 2019/11 (2) 2019/10 (5) 2019/09 (3) 2019/07 (6) 2019/06 (4) 2019/04 (3) 2019/01 (2)

2018/12 (6) 2018/10 (4) 2018/09 (6) 2018/08 (7) 2018/07 (16) 2018/06 (7) 2018/05 (7) 2018/04 (5) 2018/03 (3) 2018/02 (10) 2018/01 (6)

2017/12 (8) 2017/11 (6) 2017/10 (10) 2017/09 (12) 2017/08 (12) 2017/07 (3) 2017/06 (1) 2017/01 (4)

2016/12 (5) 2016/10 (3) 2016/09 (1) 2016/07 (2) 2016/06 (1) 2016/04 (1) 2016/02 (1) 2016/01 (2)

2015/12 (1) 2015/10 (1) 2015/09 (3) 2015/06 (1) 2015/01 (1)

2014/08 (2) 2014/07 (3) 2014/05 (1) 2014/01 (7)

2013/12 (2) 2013/11 (4) 2013/10 (1) 2013/09 (1) 2013/08 (3) 2013/07 (4) 2013/06 (5) 2013/05 (2) 2013/04 (7) 2013/03 (1)

Regexp::Trie を PHP に移植した

この記事は公開されてから1年以上経過しており、情報が古くなっている可能性があります。

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

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 や はてなキーワード のような、多数のキーワードを同時に処理しようとすると、選択が多数になるものができあがり、非常にパフォーマンスが悪いものを、トライ木を使って解決するためのものです。

元ネタはこのあたり。

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

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

s9e/regexp-builder - Packagist

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