C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[6]: Boyer-Moore の検索アルゴリズムの日本語対応

(過去ログ 129 を表示中)

[トピック内 7 記事 (1 - 7 表示)]　 << 0 >>

■76460 / inTopicNo.1)

　Boyer-Moore の検索アルゴリズムの日本語対応

▼■

□投稿者/ 細川翔 (12回)-(2015/07/12(Sun) 20:33:08)

分類:[C#]　

高速検索アルゴリズムとして、以前、Boyer-Mooreを使ったことがあります。ただし、
日本語には対応しておりません。どなたか、Boyer-Mooreの日本語対応版のC#ソースが
ありましたら、ご教示願えませんでしょうか。Sunday が更に高速との評価もある
ようですが、基本として、Boyer-Mooreの日本語対応版をチェックしたいと考えております。

よろしくお願いいたします。

なお、開発環境は、

Visual Studio Ultimate 2012
Windows 8.1 Pro
開発言語：C#
64-bit

です。

引用返信 編集キー/

■76464 / inTopicNo.2)

　Re[1]: Boyer-Moore の検索アルゴリズムの日本語対応

▲▼■

□投稿者/ 774RR (275回)-(2015/07/13(Mon) 06:13:33)

C# ってことは「文字」は UNICODE でエンコーディングは UTF-16 だから
(BMP のみ考え Surrogate を配慮しないなら)
ふつーに BM 法を実装すれば自動的に「日本語対応」だと思うんだけど。

# 日本語の厳密一致を検索してもオイラならまったくうれしくない。
# あいまい一致検索できてはじめて役に立ちそうな気がする

引用返信 編集キー/

■76469 / inTopicNo.3)

　Re[2]: Boyer-Moore の検索アルゴリズムの日本語対応

▲▼■

□投稿者/ 細川翔 (14回)-(2015/07/13(Mon) 12:06:02)

■No76464 (774RR さん) に返信

ご回答、有難うございました。

> C# ってことは「文字」は UNICODE でエンコーディングは UTF-16 だから
> (BMP のみ考え Surrogate を配慮しないなら)
> ふつーに BM 法を実装すれば自動的に「日本語対応」だと思うんだけど。

そうでしたか。実際には動作しなかったものですから、また、ネットから
日本語対応処理が必要といった記述があったものですから、そのように
考えておりました。再度、検討いたします。

>
> # 日本語の厳密一致を検索してもオイラならまったくうれしくない。
> # あいまい一致検索できてはじめて役に立ちそうな気がする
>

引用返信 編集キー/

■76471 / inTopicNo.4)

　Re[3]: Boyer-Moore の検索アルゴリズムの日本語対応

▲▼■

□投稿者/ 774RR (276回)-(2015/07/13(Mon) 14:13:57)

日本語化 (というか UTF-16 化) するとなると skiptable をどう取り扱うかが変わってくる。
BM で使う skiptable を
1. 連想配列 Dictionary<K,V> にすると記憶域消費量は減るけど検索量が増えるので遅いかも。
2. BMP のみ扱う前提で配列 [65536] にすると記憶域消費量が増える (検索量は減る)

記憶域消費量が小さいほうが CPU キャッシュに載る可能性が高くなるので
検索コスト＜キャッシュミスヒットコスト　なら 1.
検索コスト＞キャッシュミスヒットコスト　なら 2.
ってとこかな。
BMP 以外、つまり JIS 第三水準文字以上を扱うなら skiptable がでかくなりすぎて意味が無い感触。

っていうか System.String.IndexOf で性能足りないの？まずは IndexOf を試して、
そして実際に性能が足らないことを確認した上で自作するべきだと思うぞ。

引用返信 編集キー/

■76479 / inTopicNo.5)

　Re[4]: Boyer-Moore の検索アルゴリズムの日本語対応

▲▼■

□投稿者/ 細川翔 (16回)-(2015/07/13(Mon) 19:01:09)

■No76471 (774RR さん) に返信

ご回答、有難うございました。

> 日本語化 (というか UTF-16 化) するとなると skiptable をどう取り扱うかが変わってくる。
> BM で使う skiptable を
> 1. 連想配列 Dictionary<K,V> にすると記憶域消費量は減るけど検索量が増えるので遅いかも。
> 2. BMP のみ扱う前提で配列 [65536] にすると記憶域消費量が増える (検索量は減る)
>
> 記憶域消費量が小さいほうが CPU キャッシュに載る可能性が高くなるので
> 検索コスト＜キャッシュミスヒットコスト　なら 1.
> 検索コスト＞キャッシュミスヒットコスト　なら 2.
> ってとこかな。
> BMP 以外、つまり JIS 第三水準文字以上を扱うなら skiptable がでかくなりすぎて意味が無い感触。
>
> っていうか System.String.IndexOf で性能足りないの？まずは IndexOf を試して、
> そして実際に性能が足らないことを確認した上で自作するべきだと思うぞ。

膨大な文字列データから検索していますが、日本語の無いデータで実験したところ、
System.String.IndexOf では何倍も遅くなりました。

>

引用返信 編集キー/

■76495 / inTopicNo.6)

　Re[5]: Boyer-Moore の検索アルゴリズムの日本語対応

▲▼■

□投稿者/ 774RR (277回)-(2015/07/15(Wed) 18:46:08)

ちょっくらテストプログラムを作ってみたです。

おいらの作った素朴な BMH/BMS 実装より圧倒的に
System.String.IndexOf(System.StringComparison.Ordinal); のほうが速いです。
System.String.IndexOf() の比較子未指定は System.StringComparison.CurrentCulture なので遅くて当然。

Ordinal 比較でいいならたぶん自前実装する必要なしです。

引用返信 編集キー/

■76589 / inTopicNo.7)

　Re[6]: Boyer-Moore の検索アルゴリズムの日本語対応

▲▼■

□投稿者/ 細川翔 (17回)-(2015/07/26(Sun) 16:18:37)

■No76495 (774RR さん) に返信
> ちょっくらテストプログラムを作ってみたです。
>
> おいらの作った素朴な BMH/BMS 実装より圧倒的に
> System.String.IndexOf(System.StringComparison.Ordinal); のほうが速いです。
> System.String.IndexOf() の比較子未指定は System.StringComparison.CurrentCulture なので遅くて当然。
>
> Ordinal 比較でいいならたぶん自前実装する必要なしです。

ご助言有難うございました。

解決済み

引用返信 編集キー/

トピック内ページ移動 / << 0 >>

このトピックに書きこむ

過去ログには書き込み不可

- Child Tree -