Show HN: テキスト編集のための Transductive 正規表現

 (github.com/c0stya)
1 ポイント 投稿者 GN⁺ 2025-02-09 | 1件のコメント | WhatsAppで共有
  • TRRE は、正規表現にテキスト変換を直接表現する : 演算子を追加した言語拡張であり、それを実験する grep -E ライクな CLI ツール trre として提供される
  • 基本形は a:b のように入力パターンを出力パターンに変える transductive pair で、削除は x:、挿入は :x のように空文字列との変換として表現する
  • 一般的な正規表現のように 選択, 繰り返し, 文字範囲変換を使うことができ、cat:dog, [a:A-z:Z], Caesar cipher のような例が含まれる
  • 内部実装では通常の正規表現の FSA の代わりに、入力-出力の組を扱う Finite State Transducer(FST) を構築し、実験的な on-the-fly 決定化もサポートする
  • 現在は事前ビルド済みバイナリがなく、手元でビルドする必要があり、DFT の安定化、Unicode の完全サポート、ERE 機能の完成、効率的な範囲処理などが TODO として残っている

TRRE が解決しようとしている問題

  • 一般的な 正規表現 はテキストからパターンを見つけるのには有用だが、テキスト編集ではグループ処理ロジックが後処理のように働き、複雑になりがちである
  • TRRE は、パターンマッチングとテキスト修正を同じ式の中に入れるために、正規表現言語を拡張する
  • 中核となる構文は pattern-to-match:pattern-to-generate という形で、最も単純な例は a:b で a を b に変える
  • CLI ツール trre はこの概念を示す実装であり、grep -E に近い感覚で動作する

基本変換構文

  • 文字列置換は cat:dog のように記述する
    • echo 'cat' | ./trre 'cat:dog' は dog を出力する
    • (c:d)(a:o)(t:g) のように文字単位の変換でも同じ結果を作れる
  • sed のように、文字列中のすべてのマッチを置き換える用途に使える
    • Mary had a little lamb. に lamb:cat を適用すると Mary had a little cat. になる
  • 削除 は右側を空にして string_to_delete: の形で表現する
    • (x:)or は xor から x を削除して or を作る
    • a: はデフォルトの scan mode で、すべての a を空シンボルに変えて削除する
    • [aie]: のように角括弧表現を使って複数の文字を削除できる
  • 挿入 は左側を空にして :string_to_insert の形で表現する
    • (:x)or は or の前に x を入れて xor を作る
    • had a (:little )lamb は文脈の中で little を挿入する

正規表現上の変換

  • TRRE は通常の正規表現のように | による 選択 をサポートする
    • (c:b)at|(d:h)og は cat dog を bat hog に変える
  • 繰り返し演算子も変換に適用できる
    • (cat:dog)* は catcatcat を dogdogdog に変える
    • デフォルトの scan mode では cat:dog だけでも繰り返し適用され、同じ結果になる
  • 左側のパターンで繰り返しを使うと、複数の入力を消費して 1 つの出力に変えられる
    • (cat)*:dog は catcatcat を dog に変える
  • 右側のパターンで * や + を使うと 無限ループ が発生する可能性がある
    • :a* のような式は避けるべき
    • 有限回の繰り返しが必要なら :(repeat-10-times){10} のように回数を指定する

範囲変換とジェネレーター

  • 文字範囲変換は [a:A-z:Z] のように記述する
    • regular expressions を REGULAR EXPRESSIONS に変えられる
  • Caesar cipher の例が含まれる
    • [a:b-y:zz:a] は caesar cipher を dbftbs djqifs に変える
    • [a:zb:a-z:y] はそれを再び caesar cipher に戻す
  • generator のように、1 つの入力から複数の出力を作ることもできる
    • デフォルトでは可能な最初のマッチを使う
    • -a オプションを使うと可能なすべての出力を生成する
  • 例として、空入力に :(0|1){3} を適用すると 000 から 111 までの 3 ビット二進シーケンスを作れる
  • :(0|1){,3}? と -ma を組み合わせると、長さ 3 以下の部分集合のような出力を生成できる

言語仕様と演算子優先順位

  • 非公式には、TRRE は pattern-to-match:pattern-to-generate の組として定義される
  • 左側の pattern-to-match は文字列または正規表現にできる
  • 右側の pattern-to-generate は通常は文字列だが、正規表現も可能である
  • : 演算子は現在 非結合 として扱われ、TRRE:TRRE という形は文法的に許可されていない
    • この形には、TRRE が定義する関係の合成という自然な意味があるが、複雑性が増すためまだ除外されている
  • 演算子優先順位は高い順に次の通り
    • エスケープ文字 \
    • 角括弧表現 []
    • グループ化 ()
    • 繰り返し * + ? {m,n}
    • 連結
    • Transduction :
    • 選択 |

モードと貪欲性

  • trre は 2 つのモードをサポートする
    • Scan Mode: デフォルトモードで、変換を順次適用する
    • Match Mode: -m フラグを使い、文字列全体が式に一致するか確認する
  • -a オプションは可能なすべての出力を生成する
  • ? 修飾子は *, +, {,} 演算子を non-greedy にする
    • <(.:)*> は <cat><dog> から <> を出力する
    • <(.:)*?> は同じ入力から <><> を出力する
  • タグや括弧内の内容を変える例も含まれる
    • <(.*?:cat)> は <dog> <mouse> を <cat> <cat> に変える

FST ベースの実装と決定化

  • TRRE は内部的に Finite State Transducer(FST) を構築する
  • FST は通常の正規表現で使われる Finite State Automaton(FSA) に似ているが、単純な文字列ではなく入力-出力の組を扱う
  • TRRE の中核的な違いは次の通り
    • 2 つの正規言語の間の 二項関係 を定義する
    • 推論に FSA ではなく FST を使う
    • 性能のために実験的な on-the-fly 決定化をサポートする
  • 一般的な正規表現エンジンでは、決定化は非決定オートマトンを決定オートマトンに変換し、入力文字列長に対して線形時間の推論を可能にする
  • TRRE でも似たアプローチは可能だが、すべての非決定変換器 NFT を決定変換器 DFT に変換できるわけではない
    • 同じ入力ラベルを持つ 2 つの「bad」サイクルがあると、状態生成が無限ループに陥ることがある
    • こうしたループを検出する方法はあるが、コストが高い

性能とインストール状況

  • 基本の非決定版は、単純な置換では sed よりやや遅い例が示されている
    • ./trre '(vodka):(VODKA)': real 0m0.046s
    • sed 's/vodka/VODKA/': real 0m0.024s
  • 複雑な処理では、決定版 trre_dft が sed より速い例がある
    • sed -e 's/\(.*\)/\U\1/': real 0m0.508s
    • ./trre_dft '[a:A-z:Z]': real 0m0.131s
  • 事前ビルド済みバイナリはまだ提供されていない
  • インストールはリポジトリをクローンしたあと、make && sh test.sh でビルドしてテストする方式である
  • TODO には次の項目が残っている
    • 安定した DFT 版
    • 完全な Unicode サポート
    • ERE 機能の完成
      • [] 内での否定 ^
      • 文字クラス
      • $^ アンカーシンボル
    • 効率的な範囲処理

参考にしたアプローチ

関連記事

1件のコメント

 
GN⁺ 2025-02-09
Hacker News のコメント

  • このプロジェクトがどこへ向かうのか興味深い。ただ、演算子の優先順位が不自然で、このスレッドの他の人たちも同じように感じているようだ
    cat:dog は自然に、ca(t:d)og ではなく (cat):(dog) と同じだと予想してしまう

    • いろいろな面で興味深いアイデアだ
      cat:dog が (cat):(dog) ではなく ca(t:d)og のように解釈される点は私も混乱したが、正規表現をみんなが少し間違って使っているのだと思い出すと納得できた。正規表現は「本来」マッチャーではなく文字列生成器として見るべきで、だから cat|dog は形式的には {catog,cadog} のような集合に展開されると見なせる
      マッチングでは、この文字列集合をより大きなテキストに対して部分文字列マッチすればよい。問題は、実際の正規表現エンジンのほとんどがこのようには動作せず、期待に合わせたり効率のためだったりして、いろいろ奇妙な挙動をすることだ
      複数の正規表現ツールを試すと、(cat)|(dog) や (cat)|(dog)|(ca[td]og) のようなバリエーションが出てくる。だから、より形式的な観点では、cat:dog が (cat):(dog) ではなく ca(t:d)og を作るのが正しいと思う。しかし、何十年ものあいだ正規表現をユーザーの期待に合わせたマッチングツールとして乱用してきた経験のせいで、今では誰もが置換したい式を括弧で囲むようになっている
      この提案は興味深く、よく設計されているが、結局は正規表現を本来の生成器モデルに戻そうとしているように感じる。問題は文法というより、ツール側に近い
      以前この分野に近い仕事をしていた。正規表現を文字列集合の生成器として考えたことがないなら、ここで遊んでみるといい: https://onlinestringtools.com/generate-string-from-regex
      ただし、こうした生成ツールの挙動もかなり特定的だ。私が使っていたツールには、クロージャなどに制約を指定して生成器を制限する方法がいくつもあった
    • フィードバックありがとう。優先順位は私も検討中なので、変えるかもしれない
      連結の後に回すと、また別の問題が起きる可能性がある。たとえば非結合的な : では cat:dog:mouse は不正であるべきかもしれないが、どう扱うべきか確信がない
      現在のバージョンではイプシロン、つまり空文字列を挿入する。たとえば 1 文字おきに削除するには、技術的には .(.:eps) である ..: を実行できる
      echo 'abcde' | ./trre '..:' の結果は 'ace' だ
      実のところ : の結合は正規関係の合成という意味を持たせることもできるが、今は複雑すぎると考えた
    • 範囲変換も似ている。[a:A-z:Z] より [a-z:A-Z] のほうがよく、[a:b-y:zz:a] の代わりに [a-y:b-z;z:a] のような形を提案したい

  • 有限状態トランスデューサと関連ツールに関心があるなら、XFST（Xerox Finite-State Transducer）は見る価値がある。計算言語学の応用で 20 年以上使われてきた
    PARC のフィンランド人研究者が UT の授業に来て、FST でフィンランド語の形態論を処理する方法を見せてくれたことがあるが、見た目にもかなり大したものだった

    • 私もこれに言及しようとしていた。Kaplan の論文リンク: https://aclanthology.org/J94-3001.pdf
      PARC で行われた作業を説明している
    • http://hfst.github.io/ が XFST の現代的なオープンソース版だ。foma と OpenFst を包含しており、trre がやることとそれ以上のことのほとんどができるはずだ
    • Pyniniにも関心を持つかもしれない。OpenFst の Python ラッパーで、使いやすさのための機能が多数追加されたツールだ
      OpenFst はトランスデューサ用として本当に優れたライブラリだ。Johns Hopkins などで課題形式で作られた Pynini のユースケースチュートリアルも悪くない
      [1] https://www.openfst.org/twiki/bin/view/GRM/Pynini
      [2] https://www.openfst.org/

  • 標準的な正規表現の代替を探していて、特にグループのロジックが難しい、あるいは保守しやすい表現が欲しいなら、Rosie Pattern Language が合うかもしれない
    https://gitlab.com/rosie-pattern-language/rosie/-/blob/maste...
    https://rosie-lang.org/about/

  • すばらしい。1997 年ごろ、計算機科学の Diplom 論文を有限状態トランスデューサで書いたが、思っていたよりはるかに自明ではなかった
    課題は、可能な場合に合成と DFA を実装することで、合成されたトランスデューサも含まれていた。「有限状態トランスデューサの代数」で、ユースケースは形態論だった。テーマが大きく過小評価されていたので、途中あたりで終える必要があった。だから敬意を表する
    文法に関して、本当に : が連結 ab より強く結合してほしいのか気になる

    • 2000 年代初頭にバイオインフォマティクスで OpenFST を使っていた。いじるには楽しかったが、私がやっていた作業には結局役に立たなかった
      20 年経った今もプロジェクトが続いているのはうれしい: https://www.openfst.org/twiki/bin/view/FST/WebHome
    • 卒業できるかどうかを実質的に「正規表現を十分に強く扱えるか」に賭けるのは、ものすごく大胆な選択だ
    • その通り。トランスデューサは非常に古いテーマだ。なぜか正規表現のように特定の言語と強く結び付くことはなかった
      : が連結より強く結合すべきかどうかは、まだ確信がない。例を 100 個ほど見て、今の方式、つまり : が . より低いほうがより自然だと考えたが、コード上では文字通り数字を 1 つ変えるだけで変更できる。だからここに投稿したのであり、実際のフィードバックが必要だ

  • 何らかの種類の構造的な置換をしようとした瞬間、この方式では十分に見えない。たとえば s/"([^"]*)"/'$1'/ のようなことをしたい場合がある
    それに加えて、[^"] のうち ['] にマッチするものを \' に変えられるなら、さらに有用に見える
    より一般的には、正規表現はマッチ結果に対して実質的に構文木を定義するので、その木にもっと一般的な変換を実行できると便利

    • 私の理解が正しければ、次の ttre 式が望んでいることを行う:
      ":'(':(\\')|[^"'])*":'
    • 正しく理解しているなら、"..." ブロック内の内容を変え、引用符をシングルクォート ' に変えたいということだと思う
      この式で可能:
      echo '"hello world" "hello again!"' | ./trre "\":'.+?:-\":'"
      結果は '-' '-' になる
      つまり ".+?:-" という式で、"" の中のテキストを - 記号に置換しつつ、同時に周囲の引用符も変えている。疑問符は非貪欲モードを意味する

  • 「正規表現はテキスト内のパターンを見つける優れたツールだが、テキスト編集には常に不自然に感じられた」という主張にプロジェクト全体がかかっているように見えるのに、肝心の例が一つもない
    正規表現が編集においてなぜ不自然なのか理解できない。ここで編集が何を意味するのかも分からないし、人々がなぜグループで苦労するのかも分からない
    このプロジェクトには構文例は多いが、なぜ通常の正規表現より良いのかが分からない。「基本の正規表現版はこうで、自分の版はこうで、だから簡単になる」という例がいくつかあれば、プロジェクトを理解できそう

    • 正規表現は通常、一度書いたら二度と直さない性質が強いと思う。その先を見ようとするプロトタイプを作るのは、この分野のより良い未来を探る良い方法
    • 妥当な指摘。最も分かりやすい例は、文脈内でだけ置換する必要がある場合
      たとえば x と z の間にある y だけを Y に変えるには、Python ではだいたいこうする:
      pattern = r'(x)y(z)'
      replacement = r'\1Y\2'
      result = re.sub(pattern, replacement, text)
      私はこれを xy:Yz パターンで置き換えたい:
      result = re.trre('xy:Yz', text)
      x、z がもっと複雑なパターンだったり正規表現そのものだったりするなら、このアプローチのほうが便利かもしれない
    • 正規表現だけでは編集機能を提供しない、と見るのが正しい。グループはあるが、そのグループを組み合わせるには sed のような別の言語を使う必要がある
    • 置換の話。作者の構文では、置換を表現するのが、文字どおりタイプするのが、より簡単
      良いプロジェクト

  • C コードは読んでいて本当に楽しい。とても良く、今読んでいるところ
    簡単なコメントを一つだけすると、README の theory.pdf リンクが壊れている。PDF は docs/ ディレクトリにあるので、URL に docs/ を含めるだけでよい

    • フィードバックとタイポの指摘ありがとう。直した。実は自分の C の腕はかなり錆びついていて、少し不安

  • 右側に * や + を使うと無限ループになる可能性があるので避けるように、と書かれているが、単に禁止してはいけないのか?
    構文仕様が難しくなるのは理解するが、残しておく良い理由はなさそう

    • 妥当な指摘で、同意する。今は無効化したほうがよさそう
      もともとの理由は、変換器の合成という面白い演算を実装しようとしていたことだった。文字列に簡単な演算を行い、trre をフィルターのように合成できるが、まだ完成していない。なのでやはり妥当な指摘

  • 面白い探究だが、実際になぜより良いのかについての例が不足している。もちろん、私が正規表現にあまりに長く慣れすぎているだけかもしれない
    たとえば trre の (cat):(dog) が s/cat/dog よりなぜ良いのか、(x:)or が s/xor/or より何が良いのか分からない。ほぼすべての例は、頭の中では比較的簡単な正規表現に対応する
    核心的な利点があるとすればグループ論理のあたりだと思うので、例もそこに集中するとよさそう。基本構文を説明する前に、なぜそれがより良い選択なのかを先に説明したほうがよさそう
    シーザー暗号の例は、「これを逆方向に適用する」機能が非常に必要に見える。多くのテキスト置換でよくある要求で、この例では特に明確。プログラマーの頭は即座に「なぜ同じ論理を二度表現しなければならないのか?」と叫び出す
    まだ有用かどうかは分からないが、長く定着した現状維持に対する代替案を探るのは素晴らしい。たいていそうした試みは成功しない可能性も高いが、それでも探究そのものは良いものだ

  • 仕様がかなり不足しているように見える。最初の例からして変だ:
    $ echo 'cat' | trre 'c:da:ot:g'
    dog
    ここで何が起きているのか分からない。文法は次のようになっている:
    TRRE <- TRRE* TRRE|TRRE TRRE.TRRE
    TRRE <- REGEX REGEX:REGEX
    ここでのパースツリーは何なのか？ なぜ c が da に変わらないのか？ あるいは、なぜ c が削除されて da が ot に変わらないのか？
    グループ演算子より直感的な検索/置換の意味を持たせるというアイデアは良い。MS-DOS 時代には ren .log .txt のようなことができて、ちゃんと動いた。現代の bash 的な考え方ではあり得ないが、見ただけで意図は非常に明確だった

    • これは演算子の優先順位とトークン化の問題。 この言語ではトークンは単一文字で、文字と文字の間には見えない演算子がある。
      その演算子を明示的に ~ と呼ぶなら、例はこう見える:
      $ echo 'cat' | trre 'c:d~a:o~t:g'
      dog
      不要な括弧を入れるとこうなる:
      $ echo 'cat' | trre '(c:d)~(a:o)~(t:g)'
      dog
    • 文法は仕様が不足している。全体の文法はもっと複雑。現行版はドキュメントから削除した方がよさそうで、今は実際に混乱を招いている。
      なぜ c が da に変わらないのかは、すべて優先順位のため。この議論を見ると、自分が間違った優先順位を選んだようで、それが混乱を引き起こしている。
      現在の優先順位表は次の通り:
      | 1 | エスケープ文字 | \ |
      | 2 | 角括弧式 | [] |
      | 3 | グループ化 | () |
      | 4 | 単一文字 ERE の繰り返し | * + ? {m,n} |
      | 5 | 変換 | : |
      | 6 | 連結 | . (暗黙) |
      | 8 | 選択 | | |
      したがって : は .、つまり暗黙の連結より強く結合する。
    • その通り、仕様が不足している。削除の例は空文字列も REGEX になり得ることを示している。そうすると実質的にどの位置にも望むだけ多くの空文字列正規表現を含められると見なせるので、パースが無限に多くなる。
      代わりに正規表現は空であってはならないと要求すると削除の例は壊れるが、曖昧さは連結の方に移る。つまり (((c:d)(a:o))(t:g)) なのか ((c:d)((a:o)(d:g))) なのかが曖昧になる。結合性を仮定すれば、この違いは重要ではないはず。
    • 挙動の感じとしては、c:d、a: つまり空、そして ot:g のように見える。
      しかし読み返してみると確かに混乱するし、理論的には指摘は妥当。リポジトリを読んだ後では、自分も c が da に変わるべきだと信じるようになったが、確信はない