正規表現による単語リストの圧縮 (2)

括り出す対象としては先頭一致と末尾一致のほかに両端一致も考える価値があるかもしれない。たとえば

xml_set_character_data_handler
xml_set_default_handler
xml_set_element_handler
xml_set_end_namespace_decl_handler

こいつらはみんな xml_set_ で始まり _handler で終わるので

xml_set_(character_data|default|element|end_namespace_decl)_handler

こんな風にまとめられる。だがこれを構造化すると

xml_set
      ├character_data    ┐
      ├default           ┤
      ├element           ┤
      └end_namespace_decl┤
                           _handler

こんな風になり、ツリー構造からネットワーク構造へ一気にランクアップしてしまう。直感的に言って、ツリー構造なら O(n log n) で済むものがネットワーク構造だと O(n^2) 以上になっちゃいそうな気がする*1。
先頭一致の括り出しと末尾一致の括り出しを1階層ずつ交互にやっていけば大丈夫か？　でも

├aaaoooppp
├aaaxxx┐
└bbbxxx┤
         zzz

こんな風になってると aaa の部分は括り出せないので、葉までたどって途中で他の枝とくっついてないかどうかチェックする必要がありそうだ。うーむ。

*1:厳密な話ではなく、イメージとして。