正規表現キーワードのハイライト表示
なんだか手をつけてみたらあっさり作れてしまいましたので、試作品を投稿しておきます。
リファクタリング、テスト等はお任せします。
既知の制限:
山本(sgry)です。 試作までしていただきありがとうございます。 ドキュメント類も無いまま Highlighter の構造を理解されるとは、 驚きました(笑)。
さて Azuki の KeywordHighlighter が正規表現ハイライトをサポートしてこなかった理由は 内部データ構造の都合から実現が難しいことにありました(突っ込んだ話になるので後述)。 まずはご投稿いただいた試作品に目を通させていただいて、 内部事情も勘案しながら対応を決めさせていただきたく思います。
以下、データ構造上の内部事情です。 Azuki の内部データ構造は「ギャップ(分割)バッファ」というもので、 一つの大きな配列中にダミー領域が存在しています。 .NET の Regex クラスは非標準の特殊なデータ構造に対する処理がサポートされていませんので、 このダミー領域をまたぐパターンにマッチさせるのが難しくなります。 もちろん Document.Text プロパティなどでダミー領域をのぞいたデータのコピーを String 型として取り出せば確実にハイライトできますが、 全データのコピーが文字入力のたびに発生するため Windows Mobile 環境を含む低スペックマシンでは致命的に重くなる問題があります (ドキュメントの文字数がある程度大きい場合)。 これを解決する策が思いつかなかったため、未対応だったのが背景です。
手元のコードでは『2009-04-01 07:35』に書いた不具合は既にFixしています。
さて、KeywordHighlighterについてはソースコードを読んだときに複雑なことをしているなと思いました。 とはいえ、肝心のTryHighlightKeyword()ではDocumentオブジェクトに対して走査してますので、標準のRegexオブジェクトも使えます。投稿版には記述してませんが、ハイライト表現のRegexを初期化時にコンパイルをかけておくと、インクリメンタル検索などの頻繁な表示切替でもPCでは十分なスピードが出ます。
本当にトライ木のような手の込んだ手法が必要なのか。そもそもC++ではないのであまり低レベルなところまで突っ込んでもスピードがあまり期待できないですし。 私ならばRegexHighlighterに通常版も統合しちゃうかもしれませんね。KeywordHighlighterだと常に大文字小文字を区別してしまうし。単語の途中でヒットできないし。 ただし、Windows Mobile環境はPCの10分の1程度のスピードしかでないわけで、PCでの解決法が常にWindows Mobile環境でも有効とは限らないですが。
この辺(強調表示)の仕様については、EmEditorの構文強調ファイルを参考にされるといいかもしれませんよ。なんなら実行時にインポート可能にすれば!
山本(sgry)です。なかなか時間がとれず反応が遅くなり申し訳ありません。
結論から記させていただきますと、 Azukiはやはり(少なくとも当分の間は)正規表現ハイライトに対応しない方針としました。 試作までしていただいたのに恐縮ですが、なにとぞご了承ください。
以下、理由を述べます。
2009-04-01にご投稿いただいたRegexHighlighterを拝見させていただいたところ、まずTryHighlightKeyword_OneメソッドでDocument.Textプロパティを使用されていることに気付きました。前回書かせていただいたとおり、このプロパティは内部で全データのコピーを行います。そのためドキュメントが大きくなるにつれて性能が指数関数的に低下してしまうのではと思い、大きめのファイルでテストしてみました。具体的にはC#のキーワードだけをSetKeywordsで追加したRegexHighlighterを用意して、これを使ってAzukiのKeywordHighlighter.csの内容をハイライトさせました(空のドキュメントにペーストし、ハイライトが完了するまでの時間を計測。10回試行した平均値を求める。計測区間はKeywordHighlighter.Highlightメソッドの開始から終了まで)。結果、私が普段開発に使っているノートPCでRegexHighlighterは1524.4 ms、KeywordHighlighterは12.1 msとなり、残念ながら126.3倍の差がある計算になりました。
前回コメントと重複しますが、Azukiの内部データ構造はギャップバッファであるため、内部データを直接Stringオブジェクトとしてアクセスすることができません。そして、Compact Frameworkを視野に入れるとRegexクラスはString以外に対して使えません。結局のところ問題はこの点です。RegexHighlighterの速度低下の原因は間違い無くDocument.Textプロパティにありますので、これを使わずにすむ方法が考えつくまでは、やはり正規表現ハイライトには対応できないと判断いたしました。
(なお、KeywordHighlighterはDocumentを走査しますが一文字ずつ直接内部データにアクセスするためコピーを一度も行いません)
以下、レスです。
本当にトライ木のような手の込んだ手法が必要なのか。
あの構造、「トライ木」って言うんですね。知りませんでした(苦笑)。必要は、まったくありません。実際のところあの構造はキーワードハイライトをほとんど高速化しませんし、ちょっとでも速くしてみたかっただけなので、単なる趣味です(笑)。
そもそもC++ではないのであまり低レベルなところまで突っ込んでもスピードがあまり期待できない
んー、言語による速度差はアルゴリズムの差に到底及びませんから、突っ込む対象の抽象度はあまり関係無いのではないでしょうか。
私ならばRegexHighlighterに通常版も統合しちゃうかもしれませんね。
そう言われてみれば正規表現の特殊文字を全部エスケープしてしまえば正規表現でキーワードハイライトは可能ですね。調べてみるとRegex.Escapeメソッドなんてものも使えるようですし、正規表現ハイライトが実現した暁には検討してみようと思います。貴重なご提言ありがとうございます。
了解しました。ただユーザーとすれば、遅い早いとは別の話で、選択肢の一つとして選べたほうがいいんじゃないかとは思います。
私のほうでも同一の条件でテストしてみましたが、KeywordHighlighter、RegexHighlighterそれぞれで5ms、800ms程度となりました。
ただし正規表現でキーワードをマッチさせている部分は行修飾等と相性が悪く、ハイライト結果が同じになりませんので厳密に同じ条件ではありません。(というかC#向けにRegexHighlighterをそのまま使っても正しいハイライトにならない)
私のほうであれこれと試してみて775ms程度までは縮まりましたが、これ以上はちょっと方策を考えないとなー、というところでしょうか。 埋まらない速度の差があることは理解できました。 (テキストを行ごとに切り出す、テキスト全体をキャッシュするなどの対策をかけてみた)
その際にKeywordHighlighter自体にも手を入れたのですが、おっしゃるとおりギャップバッファからstringに切り出す部分が重いですね。正規表現マッチ自体の重さはちょっとこの実験では分かりませんでした。
トライ木
可逆データ圧縮技術における辞書式(lz系)と呼ばれるアルゴリズムの高速化のために使われます。身近なところではzlibなど。
言語による速度差とアルゴリズムの差
プリミティブになればなるほどネイティブと(JIT)インタプリタ駆動の差は広まるわけですが、おっしゃるとおりですね。失礼しました。
なお、私が作ったツールではRegexHighlighterでも実用上問題ないため、既に統合しています。
開発は大変でしょうがこれからもがんばってください。ではでは。
バージョン1.7でハイライト対象を絞り込む構造を実現したことに伴い、ドキュメント内容をコピーする際の速度が問題にならなくなりました。そこで、KeywordHighlighter に正規表現を使ったハイライト機能を追加しました。ひとまず実現はできたということで、本チケットはクローズさせていただきます。
現在のKeywordHighlighterでは固定文字列に対する強調表示のみで正規表現によるキーワード強調には対応していません。 各種テキスト形式のキーワードは正規表現を使わないとマッチさせられないものが多いため、ぜひともご対応いただければとお願いします。