WEKO3
アイテム
2進ディジタル探索木を用いた辞書検索法とその応用に関する研究
https://tokushima-u.repo.nii.ac.jp/records/2001852
https://tokushima-u.repo.nii.ac.jp/records/20018523a717169-bc13-46a2-bae0-7a4c7d62e27e
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
LID201205151010.pdf (22.5 MB)
|
|
| Item type | 文献 / Documents(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2012-05-15 | |||||||||||
| アクセス権 | ||||||||||||
| アクセス権 | open access | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_db06 | |||||||||||
| 資源タイプ | doctoral thesis | |||||||||||
| 出版タイプ | ||||||||||||
| 出版タイプ | NA | |||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_be7fb7dd8ff6fe43 | |||||||||||
| タイトル | ||||||||||||
| タイトル | 2進ディジタル探索木を用いた辞書検索法とその応用に関する研究 | |||||||||||
| タイトル | ||||||||||||
| タイトル | ニシン ディジタル タンサクギ オ モチイタ ジショ ケンサクホウ ト ソノ オウヨウ ニ カンスル ケンキュウ | |||||||||||
| 著者 |
獅々堀, 正幹
× 獅々堀, 正幹
WEKO
108
|
|||||||||||
| 抄録 | ||||||||||||
| 内容記述 | 本論文は，キー検索技法の中で特に2進ディジタル探索木(BinaryDigital SearchTree : BDS木と呼ぶ)を用いた辞書検索法に関する研究の成果をまとめたものであり，次の6章より構成される. まず，第l章では，緒論として，本研究の目的ならびにその工学上の意義を述べることで，本研究の意義および位置づけを明確にする.更に，本研究によって得られた諸成果を概説する. 次に，第2章では，キー検索技法の歴史的背景を述べると共に，各種キー検索技法の中でも，特に2分探索木法，多分探索木法，ハッシュ法，トライ法についての構成法を紹介し，各技法の特徴および問題点について解説する. そして，第3章では，本研究の基となるBDS木を用いたトライハッシュ法の構成法を説明する. トライハッシュ法は，ハッシュ法の特徴である高速な検索能力を継承しつつ，従来のハッシュ法では困難であった順検索を可能にする手法である. しかしながら，登録キー数が多くなると，ハッシュ法の索引部を形成するBDS木のサイズが大きくなり， BDS木全体を主記憶上に格納できなくなる.この問題点を解決するため，JongeらはBDS木を先行順ビット列と呼ばれるコンパクトなビット列に圧縮する手法を提案した.そこで，本章ではJongeらの提案した圧縮手法について解説した後，先行順ビット列上でのキーの検索・追加アルゴリズムを示す. 第4章では，第3章で紹介した先行順ビット列の時間的および空間的な問題点を明確にした後，先行順ビット列により表現されたBDS木の時間効率および空間効率を改善する手法をそれぞれ提案する.まずキー集合が大規模になると，先行順ビット列が非常に長くなり，その結果，ビット列の後方に位置するキーに対する処理の時間効率が悪化する.この時間的な問題点に対して，本論文では，BDS木の構造を階層的に分割管理し，不必要な部分木に対する処理を削減することにより，大規模なキー集合に対しても時間効率の悪化を防ぐ手法を提案する.また，先行順ビット列上でキーの検索・追加を実現するためには，BDS木のすべてのノードが2本の枝を有する必要がある.従来の手法では，1本の枝しか持たないノードに対してダミーリーフと呼ばれる擬似的な葉を持たせていた. しかしながら，大規模なキー集合に対しては，ダミーリーフ数が非常に多くなり，その結果，ビット列が非常に長くなる. この空間的な問題点に対して，本論文では，ダミーリーフを用いずに，よりコンパクトなビット列に圧縮する手法を提案する.更に，それぞれの提案手法の理論的評価，及び実験による具体的評価を与え，本手法の有効性を確かめる. また，第5章では，第4章で提案した2進ディジタル探索木を用いた辞書検索法の文書処理への応用として，2進ディジタル探索木で構成された片仮名辞書と片仮名変換ルールを用いた効率的な片仮名異表記生成手法および2進木構造で構築された文書構造データベースを用いた自動図表配置手法について述べる. 最後に，第6章では，本研究で得られた諸成果の統括を行い，今後の研究課題について述べる. |
|||||||||||
| 書誌情報 |
発行日 1997-04 |
|||||||||||
| 備考 | ||||||||||||
| 値 | 画像データは国立国会図書館から提供(2011/9/26。JPEG2000形式を本学でpdfに変換して公開) | |||||||||||
| 言語 | ||||||||||||
| 言語 | jpn | |||||||||||
| 報告番号 | ||||||||||||
| 学位授与番号 | 乙第1551号 | |||||||||||
| 学位記番号 | ||||||||||||
| 値 | 乙工第32号 | |||||||||||
| 学位授与年月日 | ||||||||||||
| 学位授与年月日 | 1997-05-09 | |||||||||||
| 学位名 | ||||||||||||
| 学位名 | 博士（工学） | |||||||||||
