| 講演名 | 2023-03-25 複数パターン長を有するマルチパターンマッチングにおけるラビン-カープ法のハッシュ関数最適化 鈴木 想生(電通大), 八巻 隼人(電通大), 三輪 忍(電通大), 本多 弘樹(電通大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 近年，多量のパターンと入力データのマッチングを行うマルチパターンマッチングの需要が高まり，その処理速度の向上は重要な課題となっている．ラビン-カープ法は，同一のパターン長であれば複数パターンを一度にマッチングできる高速なアルゴリズムであるが，異なるパターン長のパターンに対してはマッチング速度が低下する．そこで本報告では，基準データ長$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 |
| 資料番号 | CPSY2022-54,DC2022-113 |
| 発行日 | 2023-03-16 (CPSY, DC) |
| 研究会情報 | |
| 研究会 | DC / CPSY / IPSJ-SLDM / IPSJ-EMB / IPSJ-ARC |
|---|---|
| 開催期間 | 2023/3/23(から3日開催) |
| 開催地（和） | 天城町防災センター（徳之島） |
| 開催地（英） | Amagi Town Disaster Prevention Center (Tokunoshima) |
| テーマ（和） | 組込み技術とネットワークに関するワークショップ ETNET2023 |
| テーマ（英） | |
| 委員長氏名（和） | 土屋 達弘(阪大) / 鯉渕 道紘(NII) / 越智 裕之(立命館大) / / 津邑 公暁(名工大) |
| 委員長氏名（英） | Tatsuhiro Tsuchiya(Osaka Univ.) / Michihiro Koibuchi(NII) / Hiroyuki Ochi(Ritsumeikan Univ.) / / Hiroshi Inoue(Nagoya Institute of Technology) |
| 副委員長氏名（和） | 細川 利典(日大) / 中島 耕太(富士通研) / 津邑 公暁(名工大) |
| 副委員長氏名（英） | Toshinori Hosokawa(Nihon Univ.) / Kota Nakajima(Fujitsu Lab.) / Tomoaki Tsumura(Nagoya Inst. of Tech.) |
| 幹事氏名（和） | 新井 雅之(日大) / 難波 一輝(千葉大) / 井口 寧(北陸先端大) / 小川 周吾(日立) / 川村 一志(東工大) / 今川 隆司(明大) / 細田 浩希(ソニーセミコンダクタソリューションズ) / 田中 勇気(日立) / / 今村 智史(富士通) / 谷本 輝夫(九大) / 新田 高庸(会津大) / 八巻 隼人(電通大) |
| 幹事氏名（英） | Masayuki Arai(Nihon Univ.) / Kazuteru Namba(Chiba Univ.) / Yasushi Inoguchi(JAIST) / Shugo Ogawa(Hitachi) / Kazushi Kawamura(Tokyo Inst. of Tech.) / Takashi Imagawa(Meiji Univ.) / Hiroki Hosoda(Sony Semiconductor Solutions) / Yuki Tanaka(HITACHI) / / Satoshi Imamura(Fujitsu) / Teruo Tanimoto(Kyushu Univ.) / Koyo Nitta(Univ. of Aizu) / Hayato Yamaki(Univ. of Electro-Communications) |
| 幹事補佐氏名（和） | / 小林 諒平(筑波大) / 宮島 敬明(明大) |
| 幹事補佐氏名（英） | / Ryohei Kobayashi(Tsukuba Univ.) / Takaaki Miyajima(Meiji Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Dependable Computing / Technical Committee on Computer Systems / Special Interest Group on System and LSI Design Methodology / Special Interest Group on Embedded Systems / Special Interest Group on System Architecture |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 複数パターン長を有するマルチパターンマッチングにおけるラビン-カープ法のハッシュ関数最適化 |
| サブタイトル（和） | |
| タイトル（英） | Optimizing Hash Functions of Rabin-Karp Method for Multi-Pattern Matching with Multiple Pattern Lengths |
| サブタイトル（和） | |
| キーワード(1)（和/英） | パターンマッチング / Pattern matching |
| キーワード(2)（和/英） | ラビン-カープ法 / Rabin-Karp method |
| キーワード(3)（和/英） | ハッシュ関数 / hash function |
| 第 1 著者 氏名（和/英） | 鈴木 想生 / Soa Suzuki |
| 第 1 著者 所属（和/英） | 電気通信大学(略称：電通大) The University of Electro-Communications(略称：UEC) |
| 第 2 著者 氏名（和/英） | 八巻 隼人 / Hayato Yamaki |
| 第 2 著者 所属（和/英） | 電気通信大学(略称：電通大) The University of Electro-Communications(略称：UEC) |
| 第 3 著者 氏名（和/英） | 三輪 忍 / Shinobu Miwa |
| 第 3 著者 所属（和/英） | 電気通信大学(略称：電通大) The University of Electro-Communications(略称：UEC) |
| 第 4 著者 氏名（和/英） | 本多 弘樹 / Hiroki Honda |
| 第 4 著者 所属（和/英） | 電気通信大学(略称：電通大) The University of Electro-Communications(略称：UEC) |
| 発表年月日 | 2023-03-25 |
| 資料番号 | CPSY2022-54,DC2022-113 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | CPSY-451,DC-452 |
| ページ範囲 | pp.118-123(CPSY), pp.118-123(DC), |
| ページ数 | 6 |
| 発行日 | 2023-03-16 (CPSY, DC) |