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

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

基本信息

批准号：
07780341
负责人：
下薗真一
金额：
$ 0.58万
依托单位：
Kyushu Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1995
资助国家：
日本
起止时间：
1995 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07780341/
关键词：
近似アルゴリズムテキスト圧縮組合せ最適化問題

项目摘要

本研究では,組合せ最適化の考え方をもとに,情報の損失と誤差を対応させ,処理速度と高い圧縮率の保証を求められる非可逆圧縮の操作に応用可能な文字インデックスを定式化した.この文字インデックスを用いたテキスト処理における「検索」を定義し、圧縮済みテキスト上で検索処理を行う際の誤差の計量を定式化した.次に,テキスト処理に対して有効な文字インデックスを見つける問題を,組み合わせ最適化問題として定式化し,多項式時間近似アルゴリズムを設計した.文字インデックスを見つける問題に対しては,計算量の理論に基づく解析から,任意に誤差率を下げられる多項式時間近似アルゴリズムが存在しないことが明らかになった.そのため,定数誤差率の達成を目標とした多項式時間近似アルゴリズムの開発と理論的解析を行った.その結果,文字インデックスの問題に対しての定数誤差率近似アルゴリズムの開発に成功した.また,実際のテキストデータを扱って,開発した近似アルゴリズムの実際的な評価を試みた.理論的解析においては,最悪のケースを想定した解析を行っているため,対象となるデータの性質を考慮した実験的評価も重要である.また,多項式時間アルゴリズムとはいえ,その計算量オーダーが高ければ現実のシステムにおいて有用であるとは言い難く,実装上の問題となる.これらの点を検証するため,英文テキストを対象とした文字インデックスを求めるシステムと,これを用いてテキストを圧縮,また検索等の処理を行う試験的なシステムを構築し,実験を行った.その結果,アルゴリズムが十分実用的な時間で大規模なデータに対しても動作すること,理論的に確かめられた圧縮率が得られること,またアルゴリズムの持つ最悪のケースでの誤差よりも一般的にはよい解が得られることなどがわかった.

在这项研究中，基于组合优化的概念，我们制定了一个角色指数，该指数可以应用于与信息和错误丢失相对应的有损耗的压缩操作，并且需要保证处理速度和高压缩率。我们使用此字符索引在文本处理中定义了“搜索”，并在压缩文本上执行搜索处理时制定了错误的指标。接下来，我们提出了找到有效文本处理作为组合优化问题的字符索引的问题，并设计了多项式时间近似算法。对于找到字符索引的问题，据透露，没有多项式时间近似算法可以任意降低错误率。因此，我们对多项式时间近似算法进行了理论分析，目的是达到恒定错误率。结果，我们提出了针对字符索引问题的恒定错误率近似算法。我们已经成功地开发了一个模型。我们还试图通过处理实际文本数据来实际评估开发的近似算法。在理论分析中，我们进行了一项分析，假定一个最糟糕的情况，因此可以考虑到数据的属性也很重要。尽管它很难实现，但实际上很难实现，即使这是一个很难的阶段，它也很难实现。它成为一个实现问题。要验证这些要点，我们构建了一个系统，该系统可以找到英语文本的字符索引，并使用它来压缩文本和搜索处理，并进行了实验实验。结果表明，算法甚至可以在足够实际的时间内对大型数据进行算法，从而使其磨合均更好，并且该解决方案通常是更好的，并且该解决方案是更好的。