A Fast Retrieval Algorithm of Trie Structures for a Large Set of Keys

一种大键值Trie结构的快速检索算法

基本信息

  • 批准号:
    04650317
  • 负责人:
  • 金额:
    $ 1.34万
  • 依托单位:
  • 依托单位国家:
    日本
  • 项目类别:
    Grant-in-Aid for General Scientific Research (C)
  • 财政年份:
    1992
  • 资助国家:
    日本
  • 起止时间:
    1992 至 1994
  • 项目状态:
    已结题

项目摘要

In natural language processing, it needs to build a huge size dictionary. Thus, a fast and compact date stracture is required to develope practical natural language processing syatems : a automatic sentence, or document, a generation system, an automatic proof reading system, a machine translation system, a word processing system, and so on. A trie structure is a good technique that can search the longest applicable key and all prefix keys for a given string, but it takes a huge space for a large set of keys.This project porposed a compaction algorithm of trie structures and a fast retrieval algorithm even if a large set of keys. The approach proposed in this project is analyzed by theoretical evaluation and the evaluation is supported by a variety of sets of keys : EDR Japanese dictionaries, English dictionaries and compound words.The idea presented can apply to dictionaries of many natural language processing systems, so a more practical evaluation should be done in the future research.
在自然语言处理中,需要建立一个庞大的字典。因此,开发实用的自然语言处理系统需要一个快速而紧凑的数据结构:自动句子或文档、生成系统、自动校对阅读系统、机器翻译系统、字处理系统等等。特里结构是一种很好的技术,它可以搜索给定字符串的最长可应用键和所有前缀键,本文提出了一种Trie树结构的压缩算法和一种即使在密钥集很大的情况下也能快速检索的算法。本研究提出的方法在理论上得到了评价,并得到了EDR日语词典、英语词典和复合词等多种检索键的支持,该方法适用于多种自然语言处理系统的词典,因此在今后的研究中还需要进行更实际的评价。

项目成果

期刊论文数量(48)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
青江 順一,佐藤 隆士: "キー検索技法-探索技法とその応用-" 情報処理学会誌. 34. 106-113 (1992)
Junichi Aoe、Takashi Sato:“关键搜索技术 - 搜索技术及其应用” 日本信息处理学会杂志 34. 106-113 (1992)。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
J.Aoe,K.Morimoto: "A Trie Compaction Algorithm for a Lanre Set of Keys" IEEE Trans.Know-ledge & Data Engineering. (発表予定). (1995)
J. Aoe、K. Morimoto:“Lanre 密钥集的 Trie 压缩算法”IEEE Trans.Know-ledge & Data Engineering(待提交)。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
青江 順一: "キー検索技法-静的ハッシュ法とその応用-" 情報処理学会誌. 33. 1359-1366 (1992)
Junichi Aoe:“关键搜索技术-静态散列方法及其应用”日本信息处理学会杂志33。1359-1366(1992)。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
K.Morimoto, J.Aoe and H.Iriguchi18GB01 : A Method of Compressing Trie Structures: Software Practice & Experience. Vol.24, No.3. 265-288 (1994)
K.Morimoto、J.Aoe 和 H.Iriguchi18GB01:一种压缩 Trie 结构的方法:软件实践
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
J.Aoe,K.Morimato: "A Trie Compaction Algorithm for a Large Sot of Keys" IEEE Trans.Knowledge Data Engineering. (発表予定). (1995)
J.Aoe、K.Morimato:“大量密钥的 Trie 压缩算法”IEEE Trans.Knowledge 数据工程(即将发表)。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

AOE Junichi其他文献

AOE Junichi的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('AOE Junichi', 18)}}的其他基金

A fast n-gram full text search independent of document size and it application to a huge text base
独立于文档大小的快速 n-gram 全文搜索及其在庞大文本库中的应用
  • 批准号:
    10480082
  • 财政年份:
    1998
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
A Partial match technique for multi-attribute keys and its text retrieval application
多属性键的部分匹配技术及其文本检索应用
  • 批准号:
    07558273
  • 财政年份:
    1995
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for Scientific Research (A)
A Method of retrieving sentences and its intersection on large text bases
一种基于大文本的句子及其交集检索方法
  • 批准号:
    07680432
  • 财政年份:
    1995
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Construction of Context Representations Early Semantic Analysis
上下文表示的构建早期语义分析
  • 批准号:
    01550290
  • 财政年份:
    1989
  • 资助金额:
    $ 1.34万
  • 项目类别:
    Grant-in-Aid for General Scientific Research (C)
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了