From: "TOYOFUKU　Chikanobu" <toyofuku@...>
Date: 2001-07-26T14:56:28+09:00
Subject: [ruby-dev:14112] BM(Boyer-Moore) search

  豊福です。

まつもとさん
>|      /* p はいつも文字の先頭を指す */
>|      p = &big[i-llen+1];
>|      pe = p + skip[big[i]];
>|      while (p < pe) {
>|        p += m17n_mbclen(encode, *p);
>|      }
>|      i += p - p0;
>|    }
>|  ...
>|
>|でうまくいかんですかね。
> 
> pとpeが一致しなかった場合、それ以降でまずいことになるんじゃ
> ないかと推測するんですが、実際のところどうなんでしょう？

  フォローつかないですね。Subject が敬遠されて読み飛ばされて
いるかもしれないので変えました。
  いくつか BM(Boyer-Moore)法の日本語化を調べてみましたが
・まずはマルチバイトの途中からマッチすることは気にせずとも
  かくマッチする部分を探す。
・マッチした部分がマルチバイトの途中からでないかチェックする。
  （１バイトずつ戻っていきながら文字の切れ目を見つけチェック）
とやってるみたいです。
  確かに多くの検索ではマルチバイトの途中からマッチすることは
稀でしょうから後から文字先頭のチェックという方がいいですね。

  この方向に引きずられすぎかもしれませんが、
    m17n_hugahuga(enc, begin, p)
    begin から始まる文字列中を指す p が文字の１バイト目を
    指しているか
みたいのがあれば

re_compile_pattern(...)
  ...
    hogehoge = m17n_islead(enc, bufp->must[1]);
  ...
bm_search(...)
    ...
    if (j < 0) {
      if (hogehoge || m17n_hugahuga(enc, big, &big[k+1]))
        return k+1;
    }
    i += skip[big[i]];
  }
---
                                豊福
                                toyofuku@juice.or.jp