3

ボイヤームーアパターンマッチングアルゴリズム(具体的には日曜日のアルゴリズム)のバリエーションを実装しようとしています。自分自身に問いかけていました。アルファベットのサイズはどれくらいですか。

それはエンコーディング(=可能な文字数)に依存しますか、それとも私のアルファベットが256個の記号(= 1バイトで表すことができる記号の数)で構成されていると仮定できますか?

他の多くの状況では、文字をバイトとして扱うことが問題になります。これは、エンコーディングによっては文字が複数のバイトで構成される場合があるためですが、私の場合、両方の文字列が同じエンコーディングである場合、等しい文字は等しいバイトシーケンスで表されるため、それは問題ではありません。

したがって、エンコーディングを考慮に入れて、実際の文字で構成されるアルファベット(Unicodeの場合は> 90000)を想定する必要がありますか、それともテキストとパターンをバイトのストリームとして処理できますか?

4

1 に答える 1

4

マルチバイト エンコーディングは、自己同期型のバイト指向の検索ルーチンで使用できます

したがって、Boyer-Moore を次のように安全に使用できます。

  • CESU-8
  • UTF-8
  • UTF-EBCDIC

しかし、それを使用することはできません:

  • Big5
  • EUC-JP
  • GBK / GB18030
  • ISO2022
  • ヨハブ
  • Punycode
  • シフトJIS
  • UTF-7
  • UTF-16
  • UTF-32
于 2011-05-20T05:50:34.120 に答える