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

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

基本信息

批准号：
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)具体的な適用分野で必要とされる処理に圧縮したデータが適しているかを検証するために,遺伝子情報処理のシステムのプロトタイピングを行い,エンジニアリング・ワークステーションで計算実験をおこなった.結果として,実験対象が文字分類の概念に適したものであれば,厳密な文字列の区別においても非常に効果的であることがわかった.

今年，根据字符分类映射的概念，根据近似压缩算法获得了以下研究结果。首先，（1）无法恢复的文本数据丢失的近似误差的表述，并且发现字符分类绘制的映射可最大程度地减少降低字符类型数量时丢失的香农信息量。这清楚地表明，制定字符分类映射的方法是合理的。接下来，（2）为使用公式的字符分类作为组合优化问题进行近似压缩，我们分析了在多项式时间近似算法设计中字符分类映射的计算的复杂性。结果，尽管此问题中的近似值可以视为角色匹配，但可以查看两个不同的字符串。考虑到不混淆集合的问题，已经揭示了多项式时间是一个困难的问题。此外，（3）尽管使用非反馈自动机作为近似字符串匹配计算机是常见的，但在这种情况下，在计算上很难创建具有最低状态的自动机而不完全识别输入/输出。此外，（4）为了验证压缩数据是否适用于特定应用程序领域所需的处理，我们原型制定了遗传信息处理系统的系统，并在工程工作站上进行了计算实验。结果，我们发现，如果实验主题适合特征分类的概念，则在区分字符串方面也非常有效。