jjzjj

java - 用于存储单词列表的节省空间的数据结构？

coder 2024-03-22 原文

有什么比 Trie 更好的了？对于这种情况？

  • 存储约 10 万个英语单词的列表
  • 需要使用最少的内存
  • 查找需要合理，但不必快如闪电

我正在使用 Java，所以我的第一次尝试是只使用 Set。但是，我的目标是移动设备并且内存已经不足。由于许多英语单词共享共同的前缀，因此 trie 似乎是节省一些内存的不错的选择——有人知道其他一些好的选择吗？

编辑 - 更多信息 - 数据结构将用于两个操作

  • 回答:列表中有某个单词 XYZ 吗？
  • 生成 XYZ 周围有一个字母不同的词的邻域

谢谢你的好建议

最佳答案

我看到的一种用于最小化拼写词典空间的结构是将每个单词编码为:

  • 与上一个相同的字符数(一个字节)；和
  • 新的结局。

所以单词列表

HERE            would encode as    THIS
sanctimonious                      0,sanctimonious
sanction                           6,on
sanguine                           3,guine
trivial                            0,trivial

您在那里直接节省了 7 个字节 (19%)，我怀疑仅由于相邻单词(的公共(public)前缀)之间的最小距离，对于 20,000 个单词的字典，节省会类似。

例如，我在一个排序的字典上运行了一个测试程序，并将旧存储空间计算为单词长度加一(用于终止符)，新存储空间为常用长度、不常用后缀长度和一个终结者。这是该测试程序的最后一部分，显示您可以超过 50%:

zwiebacks   -> zygote      common=        old=1044662 new=469762 55.0%
zygote      -> zygotes     common=zygote  old=1044670 new=469765 55.0%
zygotes     -> zygotic     common=zygot   old=1044678 new=469769 55.0%
zygotic     -> zymase      common=zy      old=1044685 new=469775 55.0%
zymase      -> zymogenic   common=zym     old=1044695 new=469783 55.0%
zymogenic   -> zymology    common=zymo    old=1044704 new=469789 55.0%
zymology    -> zymolysis   common=zymol   old=1044714 new=469795 55.0%
zymolysis   -> zymoplastic common=zymo    old=1044726 new=469804 55.0%
zymoplastic -> zymoscope   common=zymo    old=1044736 new=469811 55.0%
zymoscope   -> zymurgy     common=zym     old=1044744 new=469817 55.0%
zymurgy     -> zyzzyva     common=zy      old=1044752 new=469824 55.0%
zyzzyva     -> zyzzyvas    common=zyzzyva old=1044761 new=469827 55.0%

为了加快查找速度，内存中有一个包含 26 个条目的表，其中包含以 a、b、c、...、z 开头的单词的起始偏移量。这些偏移处的单词始终以 0 作为第一个字节，因为它们与前一个单词没有共同的字母。

这似乎是一种 trie 但没有指针，如果树中的每个字符都有一个与之关联的 4 字节指针，这肯定会占用大量空间。

请注意，这是我在 CP/M 时代的内存比现在稀缺得多。

关于java - 用于存储单词列表的节省空间的数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/358240/

单词javacommon55.0%data-structures

有关java - 用于存储单词列表的节省空间的数据结构？的更多相关文章

  1. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  2. ruby-on-rails - Rails 常用字符串(用于通知和错误信息等) - 2

    大约一年前，我决定确保每个包含非唯一文本的Flash通知都将从模块中的方法中获取文本。我这样做的最初原因是为了避免一遍又一遍地输入相同的字符串。如果我想更改措辞，我可以在一个地方轻松完成，而且一遍又一遍地重复同一件事而出现拼写错误的可能性也会降低。我最终得到的是这样的:moduleMessagesdefformat_error_messages(errors)errors.map{|attribute,message|"Error:#{attribute.to_s.titleize}#{message}."}enddeferror_message_could_not_find(obje

  3. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  4. ruby - RVM 使用列表[0] - 2

    是否有类似“RVMuse1”或“RVMuselist[0]”之类的内容而不是键入整个版本号。在任何时候，我们都会看到一个可能包含5个或更多ruby的列表，我们可以轻松地键入一个数字而不是X.X.X。这也有助于rvmgemset。 最佳答案 这在RVM2.0中是可能的=>https://docs.google.com/document/d/1xW9GeEpLOWPcddDg_hOPvK4oeLxJmU3Q5FiCNT7nTAc/edit?usp=sharing-知道链接的任何人都可以发表评论

  5. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  6. ruby-on-rails - 在 ruby​​ 中使用 gsub 函数替换单词 - 2

    我正在尝试用ruby​​中的gsub函数替换字符串中的某些单词，但有时效果很好，在某些情况下会出现此错误？这种格式有什么问题吗NoMethodError(undefinedmethod`gsub!'fornil:NilClass):模型.rbclassTest"replacethisID1",WAY=>"replacethisID2andID3",DELTA=>"replacethisID4"}end另一个模型.rbclassCheck 最佳答案 啊，我找到了!gsub!是一个非常奇怪的方法。首先，它替换了字符串，所以它实际上修改了

  7. Ruby Sinatra 配置用于生产和开发 - 2

    我已经在Sinatra上创建了应用程序，它代表了一个简单的API。我想在生产和开发上进行部署。我想在部署时选择，是开发还是生产，一些方法的逻辑应该改变，这取决于部署类型。是否有任何想法，如何完成以及解决此问题的一些示例。例子:我有代码get'/api/test'doreturn"Itisdev"end但是在部署到生产环境之后我想在运行/api/test之后看到ItisPROD如何实现？ 最佳答案 根据SinatraDocumentation:EnvironmentscanbesetthroughtheRACK_ENVenvironm

  8. ruby - Ruby 有 `Pair` 数据类型吗？ - 2

    有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳

  9. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  10. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

随机推荐