複数パターン長を有するマルチパターンマッチングにおけるラビン-カープ法のハッシュ関数最適化

• Item type: SIG Technical Reports(1)
• 公開日: 2023-03-16
• タイトル: 複数パターン長を有するマルチパターンマッチングにおけるラビン-カープ法のハッシュ関数最適化
• タイトル / 言語: en
• タイトル: Optimizing Hash Functions of Rabin-Karp Method for Multi-Pattern Matching with Multiple Pattern Length
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 最適化
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 電気通信大学
• 著者所属: 電気通信大学
• 著者所属: 電気通信大学
• 著者所属: 電気通信大学
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications
• 著者名: 鈴木, 想生; 八巻, 隼人; 三輪, 忍; 本多, 弘樹
• 著者名(英): Soa, Suzuki; Hayato, Yamaki; Shinobu, Miwa; Hiroki, Honda
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年，多量のパターンと入力データのマッチングを行うマルチパターンマッチングの需要が高まり，その処理速度の向上は重要な課題となっている．ラビン-カープ法は，同一のパターン長であれば複数パターンを一度にマッチングできる高速なアルゴリズムであるが，異なるパターン長のパターンに対してはマッチング速度が低下する．そこで本報告では，基準データ長 ???? を導入し，全てのパターンのハッシュ値を ???? バイトデータ列から計算する新たなハッシュ関数を提案するとともに，そのハッシュ関数を用いたマッチング手法を提案する．この手法により，入力データ ???? バイトのハッシュ値から全てのパターンを一度にマッチングすることが可能となる．マルチパターンマッチングのアプリケーションとして英単語検索と侵入検知システムを想定した評価では，提案手法によりマッチング速度を従来の 12.5～50 倍に向上できることを示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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 ???? and a matching method using the hash function. This method makes it possible to match all patterns at once from the hash value of ???? 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12149313
• 書誌情報: 研究報告組込みシステム（EMB）; 巻 2023-EMB-62, 号 57, p. 1-6, 発行日 2023-03-16
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-868X
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会