关于Android的在240K单词列表使用基数树英语字典中的单词，查找问题 [英] Questions about using a Radix Tree in android for English dictionary word-lookup in 240k word-list

问题描述

在这个游戏中你追加了一封信给生长链的信件，但每个玩家都没有形成一个字。您可以选择说这一句话后，你的对手选择了一封信，追加到字母链，这需要进行检查，以一定的数据结构。我需要实现这个数据结构。

In this game you append a letter to growing chain of letters, but each player tries not to form a word. You have the option to say it's a word after your opponent chose a letter to append to the chain of letters, which needs to be checked to a certain data-structure. I need to implement this data-structure.

1. 我需要一个数据结构，是能够告诉快，如果一个词在24万字的游戏在Android设备上的列表存在。
2. 您应该可以轻松地播放长达20场比赛
3. 应该是一个Android应用程序写入

一个很好的额外功能也将可快速显示从给定词所有可能的话，但不是必须的。

A nice extra feature would also be to quickly show all possible words from a given word but is not necessary.

一个基数树好像这是个好主意，见下图。现在，我可能会后悔的时候，我把这个，因为我认为它需要太多的对象。每一个黑点，以及编号的圆圈会被重新psented为节点$ P $ 对象在我的code。

A Radix Tree seemed like a good idea for this, see the picture below. Now I might regret the time I put into this, since I think it would require too many objects. Every black dot as well as the numbered circles would be represented as node objects in my code.

一个基数树将要求在最低限度240K（240,000）节点，因此对象，每个路径的每个节点将是一个字，这将导致在240K单词列表。每个游戏将重新psented只存储一个参考在树中的当前节点，这意味着额外的游戏需要一些额外的存储$ P $。

A radix tree would require at the bare minimum 240k (240,000) nodes and thus objects, each path to every node would be one word, which would result in the 240k word list. Each game would be represented only storing a reference to the current node in the tree, meaning that an extra game requires little extra storage.

我还以为我可以实现它通过所有的单词，它和循环所有可能的字的HashMap和每个字母后缩小。这似乎是一个计算方法，其中基数树将需要较少的计算，但更大量的存储。

I also thought that I could implement it as a hashMap with all possible words in it and loop through all the words and narrow down after each letter. This seems like a computational approach, where the Radix Tree would require less computations but a lot more storage.

这是我的一个错误的假设，看看下面的图片。

This was a wrong assumption of mine, look below at the picture.

1. 是一个基数树的最佳数据结构的要求的一个给定的大多数Android设备目前使用的？ （答案/评论似乎表明它）

它是如何在内存中工作时，你有这么多的对象？难道他们都存储在RAM或还盘上？ <一href="http://stackoverflow.com/questions/18675557/what-is-the-maximum-amount-of-ram-an-app-can-use">I可以发现这是一个应用程序可以使用一个总的RAM 的16MB / 25MB / 32MB的。是不是有可能，我将投入24万对象在内存中时可达RAM 16MB的？

How does it work in memory when you have so many objects? Are they all stored in ram or also on the disk? I could find this that an app could use a total of 16mb/25mb/32mb of ram. Is it likely I will reach over 16mb of ram when putting 240000 object in ram?

您可以存储和从文件中正确运行时获取大基数树对象？它存储到磁盘在res /原始文件夹。

You can store and retrieve the large Radix Tree object during runtime from a file right? Which is stored to a disk in the res/raw folder.

可否有（比方说），50场比赛有一个哈希映射中的每场比赛，你必须使用HashMap中的一个副本，在其上缩小可能的话开，甚至可能吗？多少额外的存储空间可以在安装后的应用程序要求？

Would having (let's say) 50 games open with a hash-map in which for every game you have to use a copy of the hashmap, on which you narrow down the possible words, be even possible? How much additional storage can an application claim after installation?

根据的评论： 这似乎是我的假设是一个基数树需要更多的空间似乎错了：要看到的图像放大右键点击它，在新标签页打开的

推荐答案

一个线索/ preFIX树/基数树似乎是一个完全有效的数据结构，这种应用。如果字典是固定的（也就是说，没有的话得到补充/在播放过程中删除），你可以通过的玉米pressing共享分支。

A trie/prefix tree/radix tree seems like a perfectly valid data structure for this application. If the dictionary is fixed (that is, no words get added/deleted during play), you can save memory by compressing shared branches.

这篇关于关于Android的在240K单词列表使用基数树英语字典中的单词，查找问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！