近似圧縮アルゴリズムによるテキストデータ処理の高速化

使用近似压缩算法加速文本数据处理

• 批准号: 08780373
• 负责人: 下薗 真一
• 金额: $ 0.64万
• 依托单位: Kyushu Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-08780373/
• 关键词: 近似アルゴリズム; テキスト処理; データ圧縮; 近似文字列照合

本年度は,文字分類写像の概念に基づく近似圧縮アルゴリズムについて,以下にあげる研究結果が得られた.まず,(1)テキストデータの復元不可能な情報損失について近似誤差の定式化を行ったところ,文字分類写像は,文字種数を減らすときに失われるシャノン情報量を最小にするものであることが明らかになった.このことから,文字分類写像の定式化の方法が妥当であることが明確になった.次に,(2)組合せ最適化問題として定式化した文字分類を用いる近似圧縮について,多項式時間近似アルゴリズムの設計を行う上での文字分類写像を求める問題の計算量を解析した.結果として,この問題の近似は文字照合としてとらえると可能であるが,相異なる二つの文字列の集合を混同しないという問題として考えると,多項式時間では困難な問題となることが明らかになった.さらに,(3)近似文字列照合機械として非帰還性のオートマトンを用いる方法が一般的であるが,その場合,入出力を完全に特定しなければ最小状態のオートマトンを作ることが計算量的に困難であることがわかった.また,(4)具体的な適用分野で必要とされる処理に圧縮したデータが適しているかを検証するために,遺伝子情報処理のシステムのプロトタイピングを行い,エンジニアリング・ワークステーションで計算実験をおこなった.結果として,実験対象が文字分類の概念に適したものであれば,厳密な文字列の区別においても非常に効果的であることがわかった.

This year, the concept of text classification and image writing is based on approximate compression, and the following research results have been obtained. (1) The number of characters is reduced, the number of characters is reduced, the amount of information is minimized, and the number of characters is reduced. The method of writing images by classifying characters is proper and clear. Secondly,(2) the combinatorial optimization problem is solved by calculating the amount of computation of the problem. The result is that the problem of approximation is not the same as the problem of correspondence. The problem of approximation is not the same as the problem of correspondence. The problem of approximation is not the same as the problem of correspondence. (3) Approximate text string correspondence mechanical, non-recursive, non-recursive. (4) Specific applicable fields are necessary to reduce the processing pressure, reduce the processing time and reduce the processing time. As a result, the concept of classification of characters is suitable for the classification of characters, and the distinction between dense characters is very effective.

项目成果

M.Yamaguchi,S.Shimozono,T.Shinohara: "Finding minimal multiple generalization over regular patterns with alphabet indexing" Proceedings of the Seventh Workshop on Genome Informatics. 51-60 (1996)

M.Yamaguchi、S.Shimozono、T.Shinohara：“通过字母索引查找规则模式的最小多重泛化”第七届基因组信息学研讨会论文集。

平田耕一、下薗真一、篠原歩: "無矛盾最小OBDD問題の近似困難性について" 電子情報通信学会技術研究報告. COMP96- 9〜15. 39-48 (1996)

Koichi Hirata、Shinichi Shimozono、Ayumu Shinohara：“关于近似一致最小 OBDD 问题的难度”IEICE COMP96- 9-48 (1996)。

下薗真一: "例を無矛盾に保つための文字分類の近似困難性" 情報基礎理論ワークショップ. (1996)

Shinichi Shimozono：“字符分类中保持示例一致的近似困难”信息论研讨会（1996）。

K.Hirata,S.Shimozono,A.Shinohara: "On the hardness of approximating the minimum consistern OBDD problem" Lecture Notes in Computer Science. 1097. 112-123 (1996)

K.Hirata、S.Shimozono、A.Shinohara：“关于近似最小一致性 OBDD 问题的难度”计算机科学讲义。