权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

大規模データにおける高速検索可能な動的圧縮文字列辞書の研究

实现大规模数据高速搜索的动态压缩字符串字典研究

基本信息

批准号：
17J07555
负责人：
神田峻介
金额：
$ 1.09万
依托单位：
The University of Tokushima
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2017
资助国家：
日本
起止时间：
2017-04-26 至 2019-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17J07555/
关键词：
文字列処理データマネジメントデータ圧縮

项目摘要

今年度は，研究計画に沿ってさまざまな圧縮文字列辞書を提案し，その成果を論文やソフトウェアを通して発表した．その研究成果は主に３つである．１つ目は，既存の静的圧縮文字列辞書の構築に必要となる膨大なコストを解消した手法である．既存の静的圧縮文字列辞書では，Re-Pairと呼ばれる強力な文字列圧縮技法を適用することで，高いメモリ効率を達成している一方で，その構築時間や領域は膨大であり，大規模なデータに対して適用する場合は実用的な時間で辞書を構築することができない．そこで本研究では，文字列辞書の圧縮に文字列辞書を再帰的に適用することで，この問題を解決した．2つ目は，ダブル配列を用いた辞書構造が動的応用において抱える問題を解決する手法である．ダブル配列は，現実的な作業領域で高速な検索を提供するデータ構造であり，形態素解析器や全文検索エンジンで現在も広く用いられている．一方で，更新が繰り返されるとダブル配列は性能が低下することが知られており，必要に応じて再構成を施す必要がある．本研究では，既存の手法を用いた場合，その再構成時間が問題になることを示し，それを解決するための手法をいくつか提案した．3つ目は，メモリ効率に優れた動的文字列辞書の提案である．ここ10年，静的な圧縮文字列辞書に関する研究は実用的にも大きく進展した一方で，動的な圧縮文字列辞書に関する研究は理論に留まっている．現実的な既存の動的辞書の実装は，静的な辞書と比べて遥かに多くのメモリを使用する．そこで，本研究では，Path DecompositionとCompact Hashingと呼ばれる技法を応用することで，メモリ効率の良い動的文字列辞書を提案した．どの手法においても，実データを用いた実験により厳密に評価を与え，有効性を示した．

This year, the research project was launched along with a proposal for a compressed text dictionary, and the results of the paper were presented in a comprehensive manner. The main research results are as follows: 1. The existing static compression text dictionary is necessary for the construction of the dictionary. Existing static compression text dictionaries are suitable for re-pairing powerful text compression techniques, and high efficiency is achieved when construction time and domain are expanded when large-scale compression text dictionaries are suitable for use. In this paper, the author tries to solve the problem of the compression and re-application of the text-based dictionary. The configuration of the current operating field is high-speed search. The configuration of the morpheme parser is now available. On the one hand, update is not necessary. It is necessary to reconstitute. In this study, the existing methods are used in the case, the reconstruction time is shown, the solution is proposed, the efficiency is optimized, the text dictionary is proposed. In the past ten years, great progress has been made in the study of static and dynamic compression text series dictionaries. There are more active dictionaries in existence than there are static dictionaries in use. In this study, Path Decomposition Compact Hashing is used as a method to improve the quality of a text dictionary. The method is simple, and the method is simple.