講演抄録/キーワード |
講演名 |
2023-03-25 14:05
複数パターン長を有するマルチパターンマッチングにおけるラビン-カープ法のハッシュ関数最適化 ○鈴木想生・八巻隼人・三輪 忍・本多弘樹(電通大) CPSY2022-54 DC2022-113 |
抄録 |
(和) |
近年,多量のパターンと入力データのマッチングを行うマルチパターンマッチングの需要が高まり,その処理速度の向上は重要な課題となっている.
ラビン-カープ法は,同一のパターン長であれば複数パターンを一度にマッチングできる高速なアルゴリズムであるが,異なるパターン長のパターンに対してはマッチング速度が低下する.
そこで本報告では,基準データ長$n$を導入し,全てのパターンのハッシュ値を$n$バイトデータ列から計算する新たなハッシュ関数を提案するとともに,そのハッシュ関数を用いたマッチング手法を提案する.
この手法により,入力データ$n$バイトのハッシュ値から全てのパターンを一度にマッチングすること
が可能となる.
マルチパターンマッチングのアプリケーションとして英単語検索と侵入検知システムを想定した評価では,提案手法によりマッチング速度を従来の12.5~50倍に向上できることを示した. |
(英) |
In recent years, demand for multi-pattern matching, in which a large number of patterns are matched against input data, has increased, and improving processing speed has become an important issue.
The Rabin-Karp method is a fast algorithm that can match multiple patterns at once as long as they have the same pattern length.
In this report, we propose a new hash function that computes hash values for all patterns from a sequence of bytes of basic data length $n$ and a matching method using the hash function.
This method makes it possible to match all patterns at once from the hash value of $n$ bytes of input data.
Evaluation of the application of multi-pattern matching to English word search and intrusion detection systems shows that the proposed method improves the matching speed by a factor of 12.5 to 50 times compared to the conventional method. The proposed method can improve the matching speed by 12.5 to 50 times. |
キーワード |
(和) |
パターンマッチング / ラビン-カープ法 / ハッシュ関数 / / / / / |
(英) |
Pattern matching / Rabin-Karp method / hash function / / / / / |
文献情報 |
信学技報, vol. 122, no. 451, CPSY2022-54, pp. 118-123, 2023年3月. |
資料番号 |
CPSY2022-54 |
発行日 |
2023-03-16 (CPSY, DC) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CPSY2022-54 DC2022-113 |