ハードウェア化に適した文字列処理アルゴリズムの開発

开发适合硬件实现的字符串处理算法

• 批准号: 17700020
• 负责人: 馬場 謙介
• 金额: $ 2.24万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17700020/
• 关键词: 近似文字列照合; アルブリズム; 編集距離; 並列処理; 高速化; 文字列処理; 相同性検索; アルゴリズム; ハードウェア化; ビットパラレル

ソフトウェアアルコリスムの分野で研究されている文字列処理の高速化手法を専用ハードウェアとして実装することを目標とし,ハードウェア化に適したアルゴリズムの開発を行った.具体的には,近似文字列照合アルゴリズムの高速化について,ハードウェアの実現可能性を考慮した手法の開発を行った.単位計算で処理できるデータサイズを「ワード長」,単位計算を同時に実行できる数を「コア数」とすると,近似文字列照合の単純な解法では,計算の並列化の困難さから,ワード長やコア数が大きくなっても計算時間を短縮できない.これに対し,本研究では以下の3つの高速化手法を提案した.まず,近似文字列照合のための計算のうち,ワード長増大による高速化が可能なものを事前に計算する手法を提案した.近似文字列照合で用いる「編集距離」は,文字の挿入,削除,および置換によって定義され,このうち挿入と削除を考慮することが計算の並列化を困難にしている.置換のみを考えた場合の距離は,2つの文字列の文字一致の数える「マッチカウント問題」の解であり,ワード長の増大による高速化が可能である.本研究では,マッチカウント問題の解と近似文字列照合問題の解関係を明らかにし,マッチカウント問題の解により近似文字列照合問題の解の探索範囲の削減する手法を提案した.次に,マッチカウント問題を解くアルゴリズムとして,コア数増大により高速化を提案した.ワード長の増大による高速化の適用が可能なアルゴリズムは既存手法として既に提案されている.本研究では,文字列をアルファベットについてビット列に変換することで計算の並列化を実現し,既存手法をコア数についての高速化も適用可能になるよう拡張した.最後に,近似文字列照合問題を解くアルゴリズムとして,ワード長の増大による高速化を提案した.コア数の増大による高速化の適用が可能なアルゴリズム既存手法として既に手案されている.本研究では,既存手法で並列に行われる計算の入出力の関係を明らかにし,複数の計算を一度の計算で行う手法を提案した.一度に行うことのできる計算の数はワード長に依存する.

In the first place, we need to make a study of the text column. We are using a high-speed method to increase the speed of the system. We use the information system to install the information system, and then we need to make sure that the information is changed. For specific information, the approximate text column is similar to that of the high-speed transmission system, and the possibility of the realization of the information system will be improved. The bit calculation is used to calculate the number of data in the same time, and the approximate text column is in accordance with the solution of the equation. The calculation and parallelization is used to solve the problem, and the long-term calculation is used to calculate the short-term data. In this study, the following are the proposals for high-speed techniques. The approximate text column is similar to the text column, and the calculation method may be used in advance. The approximate text list is based on the word "edit set distance", the text is entered, cut, the definition is defined, and the data is cut. If you want to make sure that the distance is close, the text of the text column is the same, and the number of text is the same as the number of questions. In this study, we discuss how to solve a problem, how to solve a problem, and how to solve a problem. For the second time, we need to solve the problem. We need to increase the number of high-speed proposals. In order to improve the speed, we may use the existing methods to improve the speed of the system. In this study, the text column shows that the calculation is parallelized, and the existing techniques are used to increase the speed of the computer. Finally, to solve the problem of approximate text series, we need to solve the problem of high-speed speed. It is possible to use existing methods to reduce the number of people who use high speed. In this study, the existing methods are listed to calculate the input and output of the input and output, and the plural calculation is used to calculate the operation method. At one point, you need to calculate the number of people who depend on you for a long time.

项目成果

Bit-parallel Computation for wavefront Algorithm

波前算法的位并行计算

• 发表时间: 2007
• 期刊: Research Reports on ISEE, Faculty of Information Science and Electrical Engineering, Kyushu University vol. 12 (1)(印刷中)
• 作者: Hanmei E;Kensuke Baba;Yunqing Yu;Kazuaki Murakami
• 通讯作者: Kazuaki Murakami

Approximate String Matching Based on Bit Operations

基于位运算的近似字符串匹配

• 发表时间: 2006
• 期刊: Lecture Series on Computer and Computational Sciences, VSP/Brill vol. 7 (A)
• 作者: Hanmei E;Yunqing Yu;Kensuke Baba;Kazuaki Murakami
• 通讯作者: Kazuaki Murakami