没有合适的资源?快使用搜索试试~ 我知道了~
基于词的文本数据编码方法WordCode及其应用的WordTrie存储技术简介和实验结果
沙特国王大学学报使用WordTrie萨克提穆鲁甘河Ananthanarayana V.S.印度卡纳塔克邦国家技术学院信息技术系阿提奇莱因福奥文章历史记录:2018年12月14日收到2019年4月30日修订2019年5月30日接受在线发售2019年关键词:文字编码文字编码WordCodeWordTrieA B S T R A C T计算机通过为每个字符分配一个代码来处理文本数据,称为编码。字符编码技术出现于20世纪60年代后期,类似类型的技术仍然用于对文本数据进行编码。计算机只能理解字母,不能理解单词。在本文中,我们开发了一种方法,使计算机能够理解单词。我们介绍了一个基于词的编码的文本数据命名为WordCode。WordCode编码最频繁的字符集(即,单词)与动态代码组合。虽然已经提出了一些字典编码技术,但我们仍然倾向于使用字符编码(如Unicode)来编码文本数据。由于代码页的巨大尺寸和访问代码页的复杂性,尚未采用字典编码技术。在本文中,我们介绍了一个名为WordTrie的自定义trie,用于存储单词,以实现更快的编码和解码。我们以这样一种方式生成代码组合,即单词的WordCode的大小总是小于字符编码的总大小。我们的实验结果编码 文 本 文 件 从 古 腾 堡 语 料 库 , 坎 特 伯 雷 语 料 库 , 大 型 语 料 库 , 卡 尔 加 里 语 料 库 和 Silencial语 料 库 使 用WordCode显示了高达19.9%的文件大小减少相对于基于字符的编码。这种较小的文件大小意味着更少的存储空间是需要和结果更快的处理和文本数据的通信。©2019作者(S)。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。1. 介绍编 码 是 将 数 据 转 换 为 代 码 的 规 则 系 统 ( ISO/IEC 2022 ,1994)。代码是文本编码中使用的位序列代码页是基本字符与其各自代码之间的映射。文本数据被编码为代码,用于存储、处理和通信。大约有257种基于字符的文本编码方法。1这些文本编码方法定义了代码页。Unicode是一种流行的编码方法,它包含几乎所有语言的所有字符的唯一代码(Unicode联盟,2015)。Unicode有三种不同的形式,UTF-8,UTF-16和UTF-32,由通用编码字符定义*通讯作者。电子邮件地址:sakthimuruga@gmail.com(R. Sakthi Murugan)。沙特国王大学负责同行审查设置(ISO/IEC 10646,2017)。UTF-8是互联网上大约92.3%的网站使用的编码技术2迄今为止,文本数据的编码主要基于字符编码,即,文本数据的每个字符用代码表示。由于字符通常用于表示单词,因此我们开发了一种名为WordCode的编码技术,可以直接对单词进行编码。我们认为一个词是字母和数字的组合,而与语言无关。在我们的方法中,除了字母和数字之外的所有符号都用作单词分隔符。一般来说,基于单词的编码不是首选,考虑到以下因素有许多不同的语言,每种语言都有自己的一套词汇。新词经常出现。需要大量的记忆来储存所有的单词。编码将需要一个大的代码页。编码和解码将需要相当多的存储器和计算时间。我们已经考虑了所有这些问题,并开发了一种名为WordCode的技术,它可以根据单词动态编码文本1Character Sets-http://www.iana.org/2网站字符编码的使用统计,http://w3techs.com/tech-nologies/overview/character_encoding/all,2018年2月10日访问。https://doi.org/10.1016/j.jksuci.2019.05.0111319-1578/©2019作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。制作和主办:Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页:www.sciencedirect.com●●●●●924R. Sakthi Murugan,V.S.Ananthanarayana/沙特国王大学学报O我们还引入了一个名为WordTrie的自定义trie,用于存储WordCode代码页。此外,我们还提供了将新出现的单词添加到WordCode代码页的工具。我们将WordCode设计为独立于语言的模型,允许对任何语言的单词进行编码。我们设计的WordCode使文件大小始终小于或等于现有的基于字符的编码技术。对Gutenberg语料库、3Canterbury语料库、4large语料库、Calgary语料库和Silencial语料库(Arnold and Bell,1997)的文本文件进行实验,结果表明,该方法在编码文件时,实现了较小的文件尺寸这种较小的文件大小意味着需要更少的存储空间,并导致更快的处理速度。文本数据的发送和通信。本文的其余部分组织如下。第二部分介绍了本文的研究背景和相关工作。第3节提供了WordCode编码的详细描述。第4节显示了将WordCode代码页存储为WordTrie的方法第5节给出了对标准语料库中约3058个文本文件进行WordCode编码的实验结果最后,第6节总结了关于基于单词的编码的总体结论2. 背景和相关工作2.1. 背景美国信息交换标准码(ASCII)(ISO/IEC 646,1991)是大多数文本编码方法的基础,包括Unicode。ASCII是编码128个字符的七位代码,包括数字、小写字母和小写字母、基本标点符号和控制代码(Gorn等人,1963年)。控制码起源于电传打字机,没有相关的编码。ASCII和Unicode分别有33和64个控制码。控制代码包括用于文本操作和通信任务的代码。为文本操作和通信任务定义一个代码页会浪费大量的代码空间。不用于文本表示的Unicode控制代码在表1(ISO/IEC 8859,1998)中被列为通信任务代码。由于互联网和工业中的文本数据呈指数级增长,因此需要进行文本数据压缩。编码文件通常被压缩以用于有效的存储和传输。熵编码和字典编码是用于压缩基于字符的文本数据的流行技术。Knuth(1985)的Huffman编码和Witten等人(1987)的算术编码是两种流行的熵编码技术。该模型采用变长码代替定长码进行数据压缩,最短的码用于最常用的符号。Ziv等人的LZ77和LZ78。(1977,1978)是两种流行的字典编码器。这个模型压缩数据的方法是,用头中的一个副本替换重复出现的数据,并在所有后续出现中继续引用它这些数据压缩和数据解压缩模型的主要缺点是它们给系统引入了开销。在我们的工作中,我们减少了这些类型的压缩和解压缩方法的工作量,直接根据单词对文本进行编码。在这篇文章中,我们提出了一种对单词进行编码的机制,为了有效的存储和访问,我们引入了一个定制的trie,我们称之为WordTrie。Trie是一种有序的树数据结构其中节点的所有后代具有与每个节点相关联的公共前缀串(Aoe等人,1992; Fredkin,1960)。3古腾堡计划,https://www.gutenberg.org/,2017年7月17日访问。4The Canterbury Corpus,http://corpus.canterbury.ac.nz/,2017年7月17日访问表1通信任务代码列表。SL. 号Unicode小数描述1U + 00011标题起始2U + 00044传输结束3U + 00055询问4U + 00066承认5U + 00077贝尔6U +000E14移出7U +000F15转变8U + 001016数据链路换码9U +001117设备控制一10U +001218设备控制二11U +001319设备控制三12U +001420设备控制四13U +001521否定确认14U +001622同步空闲15U +001723传输块16U +001824取消17U +001925培养基结束18U +001A26替代19U +001B27逃脱2.2. 相关作品存在用于通过替换来自字典的单词来压缩文本数据的一些现有方法Azad等人(2010年)设计了一个模型,通过使用19位固定代码的英 语 单 词 查 找 表 来 减 少 文 件 大 小 该 模 型 的 代 码 空 间 被 限 制 为524288,并且只能容纳与大小写无关的英语基本词。存储所有单词的代码页将具有相当大的存储成本。因为搜索是线性的,所以这种技术消耗大量的计算时间,最坏的情况是n,其中“n”是字典中的单词总数。Grabowski和斯瓦查(二零一零年)推荐语言-独立的基于单词的文本压缩和解压缩。这是一种字典编码器,其中字典被生成并作为前缀附加到压缩文件。Waidyasooriya等人(2014)考虑了一种词对编码方法,其中最常见的字符对被替换为数据中未使用的字符此方法将其编码限制为仅两个字符。由于此方法使用头来存储编码,因此此方法可以称为压缩方法。Sinaga et al.(2015)还设计了一种基于trie的编码,用于编码符号、连词、前缀、后缀、词缀和最常用的印度尼西亚语单词。虽然它们有16位长度的码字,可以容纳65536个代码,但它们的初始代码页仅限于903个代码。单词在trie中在16位代码中,他们使用了2位来区分单词大小写,这再次将代码页大小减少到16384个代码,但他们遗漏了中间大写的单词,例如Kalajdzic等人(2015年)提出了一种短消息压缩技术,通过构建和共享一个小型词典,其中包含1110个条目,这些条目是从大量消息中出现的最频繁单词列表中构建的。此方法没有足够的代码来映射所有单词,在这种情况下,在字典中找不到单词的可能性非常高考虑到现有系统的局限性,我们设计了代码页大小为679亿的WordCode,在第3节中详细讨论。3. WordCodeWordCode是基于字符的编码技术的扩展,用于基于字符和单词对文本进行编码。要实现WordCode,我们需要构造代码页并在类似于Unicode的设备上配置它由于大多数现代设备都配置了Unicode,因此WordCode使用R. Sakthi Murugan,V.S.Ananthanarayana/沙特国王大学学报925使用Unicode代码的动态基于上下文的编码,如3.1节所述。第3.2节说明了Word- Code代码页的构造第3.3节描述了WordCode的操作3.1. 动态上下文编码今天的网页通信方法与电传打字机的方法不同。由于电传打字机传送打字信息,因此为文本表示和通信任务定义了一个公共代码页。今天使用通用代码页(如ASCII和Unicode)来处理通信和文本数据操作会导致开销。根据用途定义单独的代码页并动态使用它们将减少这种开销。在WordCode中,我们将Unicode用于通信任务的控制代码分离到单独的代码页,然后使用这些代码来表示WordCode的单词。如表1所示,通过WordCode使用Unicode的通信任务代码的方法在第3.2节中描述。3.2. WordCode构造要构建WordCode代码页,应生成一个单词列表,并且必须为所有单词分配一个唯一的代码。次第3.2.1节描述了单词列表生成的方法,第3.2.2节概述了代码生成的过程,第3.2.3节说明了将代码分配给单词的方法3.2.1. 词表生成单词列表是从万维网(www)上使用的频繁单词中生成的网页是使用类似于搜索引擎的网络爬虫从www上抓取的。从网页中提取的话连同他们的出现频率。一个词是字符和数字的组合,不包括符号和特殊字符。单词区分大小写;即,单词频率小于阈值的单词在创建单词列表时被过滤掉。3.2.2. 代码生成单 个 代 码 页 用 于 对 Unicode 字 符 和 WordCode 字 进 行 编 码 。Unicode有6400个代码点,从57344到63743,保留给私人第三方使用,以定义他们的字符,但我们没有使用这些代码,因为它需要两个字节,并限于6400个代码。Unicode为通信任务定义的单字节控制代码用于对WordCode中的单词进行编码。因为在表1中只有19个控制码是纯粹为通信任务定义的,所以它们可以用作前缀,一个或多 个 字 节 码 用 作 后 缀 , 以 表 示 WordCode 中 的 字 。 表 2 显 示 了Unicode表2Unicode的大小Unicode字节完全码0–127112812826129955296–57343–2048(保留)表3WordCode结构。其字节大小由WordCode用作后缀。分别有128和61299个一字节和两字节的代码这61427个代码可以与19个前缀代码(通信任务代码)结合使用,以将单词编码为WordCode。从55296到57343的2048个UTF-16编码不能使用,因为这些编码是Unicode保留表3显示了WordCode的结构,其大小以字节为单位。表3中的前缀是Unicode的通信任务代码,如表1所示。表3中的单字节Unicode是从0到127的Unicode UTF-8代码,如表2所示,每个代码占用一个字节。表3中的双字节Unicode是从128到55295和57344到63474的Unicode UTF-16代码,每个代码在内存中占用两个字节,如表2所示。WordCode是由前缀码后面跟着一个字节和两个字节Unicode的组合形成的。WC 1指的是WordCode type-1,前缀代码由一个字节的Unicode组 成 。 WC 2 表 示 具 有 前 缀 代 码 以 及 一 对 单 字 节 Unicode 的WordCode类型-2。WC 3指向WordCode type-3,其前缀代码后跟一个单字节的Unicode代码和一个双字节的Unicode。WC 4指的是WordCode type-4,其前缀代码伴随着一个双字节Unicode和一个单字节Unicode。WC 5意味着WordCode type-5,前缀码与后续的一对双字节Unicode。第一个前缀码仅用于类型WC1,其余18个代码用于类型WC2、WC3、WC4和WC5。从“1-0”到“1-127”的代码属于WC1类型。代码中的连字符(-)表示代码的前缀和后缀之间的分隔,并且不会出现在实际的代码页中。从“4-0.0”到“27- 127.127”的代码点(.)在代码中是为了说明两个后缀代码之间的分离,并没有出现在真正的代码页中。从“4-0.128”到“27-127.63474”的代码属于WC 3类型。从“4-128.0”到“27-63474.127”的代码从“4-128.128”到“27-63474.63474”的代码WordCode类型WC1到WC5总共可以编码679亿个单词。第3.2.3节详细描述了将这些代码分配给第3.2.1节中生成的单词。3.2.3. 码分配图 1显示了包含字符和单词代码的WordCode代码页的模型。字符的代码与Unicode相同,单词的代码是在3.2.2节中生成的代码。图2展示了WordCode代码页的一个示例。在图2中,列类型、字节和代码数是为了说明而给出的,并且不包括在WordCode的实际代码页中。这里,代码从“1-0”到“27-63474.63474”的代码在3.2.1节中生成的单词首先根据长度排序,然后根据频率排序。不考虑长度小于或等于两个字节的单词,因为我们使用至少两个字节来表示WordCode中的单词。在3.2.2节中生成的代码被分配给基于霍夫曼编码的具有以下条件的字1. WordCode的长度小于字符代码的总长度2. 高频词接收较短的WordCode。WC2h prefixih One-byte Unicodei h One-byte Unicodei3 4-0.0 to27-127.127 294912WC3h prefixih One-byte Unicodei h Two-byte Unicodei4 -0.128 to27-127.63474 141232896WC4h prefixih Two-byte Unicodei h One-byte Unicode i 4-128.0 to27-63474.127 141232896WC5h prefixih Two-byte Unicodei h Two-byte Unicodei5 4-128.128 to27-63474.63474 67636213218类型WordCode模板字节范围完全码WC1hprefixih单字节Unicodei21-0至1-127128926R. Sakthi Murugan,V.S.Ananthanarayana/沙特国王大学学报Fig. 1. WordCode代码页模型。图二. WordCode的示例代码页具有不同情况的单词的代码是不同的,即,如图2所示,单词虽然WordCode代码页可以容纳679亿(67918974050)个单词,但我们在抓取过程中只发现了310万(31,90,612)个单词,并且我们只为310万个单词创建了代码页。剩余的代码保留给在将来的爬网中可能找到的新单词3.3. WordCode操作一旦代码页准备好了,它就在系统之间共享,这样系统就可以使用这个代码页来编码文本数据。 图 3显示了WordCode的内务处理。一旦WordCode服务器图三. WordCode管理生成代码页,它被配置为类似于Unicode的设备然后,文本数据被编码、存储、处理并作为WordCode编码文件进行通信。同时,Word-Code服务器还检查互联网上新生成的单词.这些新生成的单词会定期贡献给WordCode代码页的下一个新找到的单词被分配到代码页中的未保留代码,并且配置了WordCode的设备向WordCode服务器发出更新请求,以更新到WordCode代码页的最新版本在Web环境中,如果客户端对网页进行HTTP请求,则浏览器将编码格式传输为WordCode以处理文本数据。服务器用WordCode编码的网页响应用户机器,其版本小于或等于客户端在客户端,WordCode编码的网页显示在浏览器中。将Unicode编码文件编码为WordCode的方法在第3.3.2节中描述,将WordCode编码文件解码为Unicode编码的过程在第3.3.3节中描述。3.3.1. Unicode和WordCode表4显示了示例文本“The apple is good. “以Unicode和WordCode编码。在Unicode中,每个字符由代码,但在WordCode中,每个单词都由代码解释,而代码页中没有的符号,特殊字符和单词则以Unicode编码。在例句中,第一个单词单词特殊字符空格“”和句号“”。’ aredenoted using the same Unicode codes ‘在例句中,单词单词因为单词R. Sakthi Murugan,V.S.Ananthanarayana/沙特国王大学学报927在例句中,单词在Unicode中,单词3.3.2. WordCode编码算法1是WordCode编码算法(WEA)。WEA接收Unicode编码的文件,并将其转换为WordCode编码的文件WEA中的编码继续进行,直到它到达文件的末尾()。如果正在读取的字符是WordCode使用的前缀代码,则WEA返回Uni- code文件,而不使用WordCode对文件进行编码。WEA检查读取的字符是否属于单词字符。单词字符是字母(英语),数字(英语)和字母(英语)。在WEA读取单词字符之前,它会继续将单词字符追加到一旦WEA遇到除了单词字符之外的新字符如果是,WEA检查“NewWord”在WordCode代码页中是否如果它确实有一个关联的WordCode,则它是一个单词命中,然后WEA写入'New-Word'的WordCode然后,WEA继续从Unicode文件中读取下一个字符,并重复该过程,直到它到达Unicode。读第一个字符因为它是一个单词字符,所以它将字符算法继续读取下一个字符因为它是一个单词字符,所以它包括字符算法扩展到读取下一个字符因为它是一个单词字符,所以它将字符' e '添加算法继续读取下一个字符因为它不是单词字符,所以算法检查“NewWord =The”在代码页上是否由于该算法为已读取的“space”写入Unicode代码类似地,该算法读取单词但是,当算法读取单词“is” 并搜索WordCode代码页时该算法继续向下,直到它完成从输入Unicode文件中读取所有字符。3.3.3. 字码解码算 法 2 是 WordCode 解 码 算 法 ( WDA ) 。 WDA 接 收 使 用WordCode编码的文件,并将其转换为使用Unicode编码的文件。WDA中的解码继续进行,直到它到达解码器。如果10到输出文件。如果算法1:WordCode编码算法(WEA)前缀码的码长通过方法“get-CodeLength”获得在达到代码长度之前,将从WordCode文件中读取下一个代码The单词以Unicode代码写入文件。WDA一直持续到它到达第二个节点。算法2:字码解码算法(WDA)假设输入Unicode文件只包含一个句子“The apple is good”。’, asshown in 算法开始928R. Sakthi Murugan,V.S.Ananthanarayana/沙特国王大学学报表4以Unicode和WordCode编码的示例文本文本不He一ppLeI sG oOD.Unicode84104101 329711211210810132105 11532103111111100 46WordCode1-3321-12732105 115324-0.146假设输入的WordCode文件只包含一个句子“The apple is good.”’,as in 算法开始读取第一个代码因为它是一个前缀代码,所以它获取前 缀 代 码 “1” 的 代 码 长 度 对 于 前 缀 该 算 法 读 取 下 面 的 与 'WordCode=1-3 '关联的单词算法读取下一个代码因为它是一个字符代码,所以它写的字符代码与Unicode代码相同。类似地,算法将下一个代码读为' 1 ',由于它是前缀代码,因此它将前缀代码与后缀代码一起添加以创建与' WordCode = 1-127 '关联的单词该算法将继续执行,直到完成从输入WordCode文件中读取所有代码4. WordTrie如果所有单词的代码页都以线性方式存储,如图所示。 2,那么它将需要相当大的存储器和计算时间来编码和解码WordCode。为此,我们提出了一种混合存储与一个trie和数组命名为WordTrie存储所有的话。这里,单词被分割成字符并作为节点存储在trie中,其中具有相同起始子串(前缀)的单词将共享从根开始的trie分支的公共节点,从而减少所需的冗余。在计算时间和计算空间之间存在权衡,即是否具有较低的计算时间通过增加存储要求或通过增加计算时间来具有更少的存储为了解决这个问题,我们提出了两种形式的WordTrie;一种具有优化的计算时间,在第4.1节中讨论,另一种具有优化的计算空间,在第4.2节中讨论。WordCode代码可以显式存储在WordTrie中,也可以计算。在时间优化方法中,WordCode代码存储在WordTrie中,从而通过减少计算时间来增加计算在空间优化方法中,计算WordCode,因此增加了计算时间,从而减少了计算空间。4.1. 时间优化的WordTrie图4示出了具有优化的计算时间的WordTrie。在这里,单词被分割成字符并存储为trie中的节点,第一个字符连接到根节点。具有相同起始子串(前缀)的单词将共享从根开始的trie分支的公共节点。时间优化的WordTrie中的数组是一个结构数组,每个条目包含两个字段:WordCode代码和将WordCode代码连接到其相应单词的指针。数组中的指针包含trie节点的地址,trie节点包含对应于WordCode代码的单词的因此,如果在WordCode代码页中有WordCode代码按代码分配顺序存储。包含trie中单词的最后一个字符的节点链接到数组中相应的WordCode代码。连接trie节点的链接是双向的,从trie指向数组的链接是单向的。见图4。 WordTrie:计算时间优化。R. Sakthi Murugan,V.S.Ananthanarayana/沙特国王大学学报929奥什×奥什奥什遍历时间优化的WordTrie以找到与单词相关联的WordCode代码的方法在第4.1.1节中描述。遍历时间优化的WordTrie以找到与WordCode代码相关联的单词的方法在第4.1.2节中描述。4.1.1. 遍历时间优化的WordTrie查找与单词为了在时间优化的WordTrie中找到给定单词的WordCode,我们需要从根遍历WordTrie。我们确定根节点是否有一个与单词的第一个字符匹配的子节点,这个过程一直持续到遇到单词的最后一个字符。最后,我们检查是否有从最后一个字符节点到数组的链接。如果是这样,它是一个单词命中,它将从数组中检索WordCode。如果在trie中无法成功遍历单词,或者从trie中单词的最后一个字符到数组没有链接,则为单词未命中。考虑单词单词的第一个字符是下一个字符是最后一个字符是最后,检查是否有从最后一个字符节点' e '到数组的设遍历时间优化的WordTrie以找到与单词相关联的WordCode代码使用p n,因为对于单词中的每个字符,在每个级别的WordTrie中最多4.1.2. 遍历时间优化的WordTrie查找与WordCode代码为了在时间优化的WordTrie中找到给定WordCode的单词,我们需要从数组中遍历WordTrie考虑需要在时间优化的WordTrie中找到单词的 WordCode 获取单词代码为“1-3” 的数组的节点节点中与WordCode代码匹配的指针包含trie节点的地址,该trie节点包含与WordCode关联的单词的最后一个字符在这种情况下,指针' p 4',这是在具有字代码' 1-3 '的数组的节点,包含trie节点的地址,该trie节点包含与字代码相关联的字的最后一个最后一个字符节点的trie是遍历到根的trie取得的字与代码相关联访问地址“p 4”中的节点它将查找' e '的父节点因为没有到达根节点,所以它将再次查找' h '的父节点,因为没有到达根节点,所以它将再次查找' T '的父节点一旦到达根节点,遍历的路径的反向将提供与代码相关联的单词,并且单词遍历时间优化的WordTrie以找到与WordCode代码相关联的单词使用1,因为一旦我们获得WordCode,我们就获得具有WordCode的数组的索引,并遍历回到根节点以获得与WordCode相关联的单词4.2. 空间优化的WordTrie图5是具有优化的计算空间的WordTrie,其中单词被分成字符并存储为trie中的节点,其中第一个字符连接到根节点。具有相同起始子串(前缀)的单词将共享从根开始的trie分支的公共节点。空间优化的WordTrie中的数组是指针数组;即,对于包含Trie中单词的最后一个字符的节点的地址以代码分配给单词的顺序存储在数组中。此外,包含trie中单词的最后一个字符的节点被链接到数组中它们各自的地址。WordCode代码是动态计算的基础上,从持有数组中的字的最后一个字符的节点使用P2WC和WC2P算法的指针,如第4.2.1和4.2.2节中所述,分别。图6显示了将WordCode代码映射到数组位置的模板。连接trie节点的链接是双向的,从trie指向数组的链接是单向的。图五. WordTrie:计算空间优化。930R. Sakthi Murugan,V.S.Ananthanarayana/沙特国王大学学报ω遍历空间优化的WordTrie以找到与单词相关联的WordCode代码的方法在第4.2.3节中描述。遍历空间优化的WordTrie以找到与WordCode代码相关联的单词的方法在第4.2.4节中概述。4.2.1. 位置到字代码(P2WC)算法3是位置到字代码(P2WC)算法,其用于将空间优化的WordTrie中的阵列的位置转换为字代码。方法getPre- fixCode(i)用于从表1中获得第i个前缀代码。方法get1ByteCode(j)用于从表2中获得第j个单字节代码,方法get2ByteCode(k)用于从表2中获得第k个双字节代码。如果位置小于或等于128,则它属于类型WC1。对于WC 1,前缀值是第一个前缀代码,后缀值是位置的单字节代码。Append方法追加前缀和后缀值,使其成为WordCode。算法3:位置到字代码(P2WC)见图6。 位置到WordCode映射。然后,前缀索引被计算为1加上位置与后缀代码的总数的比率方法getPrefixCode(Prefix Index)用于从表1中获取Prefix代码。一个名为“temp”的临时变量Suffix_1被计算为' temp '与Suf-fix_ 2(128)中的代码总数的比率Suffix_2的计算方法是“临时”占Suffix _ 1中代码总数的百分比最后,Append方法追加Prefix、Suffix_1和Suffix_2值,使其成为WordCode。如果位置大于295040且小于或等于141527936,则其类型为WC3。如果位置大于141527936且小于或等于282760832,则其类型为对于类型WC3和WC4,WordCode的计算方式与类型WC2相同,只是WC3中的Suffix_2和WC4中的Suffix_1的总数为16299(表3中指定的双字节代码总数)。如果位置大于282760832 且小于或等于67918974050 , 则 其 类 型 为 WC5 。 最 后 , 该 方 法 返 回 位 置 的WordCode代码。如果位置大于128且小于或等于295040,则其类型为WC 2。首先,位置值从129(1加上WC 1的代码总数4.2.2. WordCode到位置(WC2P)算 法 4 是 WordCode to position ( WC2P ) 算 法 , 其 用 于 将WordCode 代码转换为空间优化的 WordTrie 中的阵列的位置。getSize(WC)方法用于获取WordCodeWC的字节大小,getPrefix(WC)方法用于从WordCode中获取前缀部分如果WordCode是WC1类型,则getSuffix(WC)方法用于从WordCode获取后缀部分 。 如 果 WordCode 的 类 型 为 WC2 、 WC3 、 WC4 或 WC5 , 则getSuffix_1(WC)方法用于从WordCode获取第一个后缀部分,getSuffix_2(WC)方法用于从WordCode获取第二个后缀部分。getPIndex ( Code ) 方 法 用 于 从 表 1 中 获 取 Code 的 前 缀 索 引 。get1BIndex (Code )方法从表2中获取Code 的单字节后缀索引。get2BIndex(Code)方法是R. Sakthi Murugan,V.S.Ananthanarayana/沙特国王大学学报931---用于从表2中获得代码的两字节后缀索引。如果WordCode的大小为两个字节,则它属于WC1类型后缀部分的索引将提供类型WC1的数组的位置如果WordCode的大小为3个字节,则它属于WC2类型如果字代码的大小是四个字节,后缀1的大小是一个字节,那么它是WC3类型如果WordCode的大小为4个字节,Suffix1的大小为2个字节,则它属于WC4类型如果WordCode的大小为5个字节,则它属于WC5类型。WC2、WC3、WC4和WC5类型的位置被计算为前一级的代码数与Prefix 、 Suffix_1和 Suffix_2的乘积之和。最后,该方法返回WordCode代码的位置算法4:WordCode to Position(WC2P)4.2.3. 遍历空间优化的WordTrie查找与单词为了在空间优化的WordTrie中找到给定单词的WordCode,我们需要从根遍历WordTrie。考虑单词单词的第一个字符是根节点到节点下一个字符是最后一个字符是并从节点“h”遍历如果从最后一个字符节点到数组有一个链接,则检索数组中的位置。在这种情况下,有一个从最后一个字符节点' e '到数组的链接使用P2 WC算法将位置4.2.4. 遍历空间优化的WordTrie查找与WordCode代码为了在空间优化的WordTrie中找到给定WordCode的单词,我们需 要 从 数 组 中 遍 历 WordTrie 考 虑 WordCodeWC2P 算 法 用 于 将WordCode代码转换为数组中的位置WordCode数组中的包含字的最后一个字符的trie节点的地址最后一个字符节点被遍历到trie的根,以获取与代码相关联的单词。在这种情况下,首先访问地址“p 4”中的节点然后,查找' e '的父节点因为没有到达根节点,所以再次查找' h '的父节点因为没有到达根节点,所以再次查找' T '的父节点一旦到达根节点,遍历的路径的反向将提供与代码相关联的单词,并且单词5. 实验结果5.1. WordCode代码页实现由于所有网站中有53.4%使用英语,因此进行了实验设置和评估,以使用英语文本编码文本文件。一个词是由一系列的统一码组成的,与语言无关这项工作也可以通过将其他语言的单词添加到WordTrie并分配后续未分配的WordCode代码来扩展在第3.3.2节所述的WordCode编码过程中,对于英语,单词字符被视为一组字符(UTF 97至122)、数字字符(UTF 65至90)和数字(UTF 48至57)。对于其他语言,它们各自的UTF代码也将包括在内。WordCode仅对包含单词的文本执行得更好。我们可以通过爬取整个www来获得Word-Code代码页所使用的完整单词列表,但是由于资源有限,我们将我们的爬取限制在Wikipedia6和DMOZ7 网站。在www上使用的大多数单词都可以在Wikipedia和DMOZ上找到。我们已经解析了Wikipedia和DMOZ网页中连续出现的单词字符,即,字符(A Z),数字(09)。我们获得了长度范围从1到29的单词,包含英语单词,来自各个领域的单词和用于表示HTML语法的单词。因为WordCode使用最少两个字节来表示一个单词,所以我们已经删除了长度为1和2的单词。我们还删除了在整个抓取中出现不到100次的单词。5网站内容语言的使用统计,https://w3techs.com/tech-nologies/overview/content_language/all,2018年2月10日访问。6Wikipedia,The Free Encyclopedia,https://en.wikipedia.org,2017年8月24日访问。7DMOZhttps://www.dmoz.org/932R. Sakthi Murugan,V.S.Ananthanarayana/沙特国王大学学报表5生成的字数单词长度单词数量语料库、大型语料库、卡尔加里语料库和Silencia语料库。这些corpora包含测试无损数据压缩算法的基准。表6显示了测试的大小比较346143669Unicode编码和WordCode编码的数据文件表6还包括从每个语料库中获取的文件数量,5291886与现有文件的总文件大小和总文件大小6789428831479778471482404327在WordCode编码之后。因为古腾堡语料库的总文件大小是以百万计的,而所有其他语料库的总
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功