在 Java 树状图中查找元素位置

dictionary iterator java treemap sortedmap

2022-09-02 01:07:44

我正在使用 Strings 的 TreeMap，并用它来实现单词的 Dictionay。TreeMap<String, String>

然后，我有一个文件集合，并希望在字典定义的向量空间（单词空间）中创建每个文件的表示形式。

每个文件都应该有一个向量来表示它，具有以下属性：

矢量应具有与字典相同的大小
对于文件中包含的每个单词，矢量应该在对应于字典中单词位置的位置中具有1
对于文件中未包含的每个单词，矢量应该在与字典中的单词位置相对应的位置有一个 -1

所以我的想法是使用 a 来实现这些向量。（这种表示集合中文档的方式称为布尔模型 - http://www.site.uottawa.ca/~diana/csi4107/L3.pdfVector<Boolean>)

我在创建此向量的过程中遇到的问题是，我需要一种方法来查找字典中单词的位置，如下所示：

String key;
int i = get_position_of_key_in_Treemap(key); <--- purely invented method...

1）有没有这样的方法可以在树图上使用？如果不是，你能提供一些代码来帮助我自己实现它吗？

2）TreeMap上是否有迭代器（按键的字母顺序排序），我可以获得位置？

3）最终我应该使用另一个类来实现字典吗？（如果你认为使用TreeMaps，我无法做我需要的事情）如果是，哪个？

提前致谢。

新增部分：

dasblinkenlight提出的解决方案看起来很好，但存在复杂性问题（由于将键复制到数组中，因此与字典的尺寸呈线性关系），并且为每个文件执行此操作的想法是不可接受的。

对于我的问题还有其他想法吗？

答案 1

构建树状图后，将其排序的键复制到数组中，然后使用 Arrays.binarySearch 在 O（logN）时间内查找索引。如果需要该值，也可在原始地图上进行查找。

编辑：这是您将密钥复制到数组中的方式

String[] mapKeys = new String[treeMap.size()];
int pos = 0;
for (String key : treeMap.keySet()) {
    mapKeys[pos++] = key;
}

答案 2

另一种解决方案是使用的 headMap 方法。如果单词存在于中，则其头映射的大小（） 等于字典中该单词的索引。与我的其他答案相比，这可能有点浪费。TreeMapTreeMap

以下是您在Java中编码的方式：

import java.util.*;

class Test {
    public static void main(String[] args) {
        TreeMap<String,String> tm = new TreeMap<String,String>();
        tm.put("quick", "one");
        tm.put("brown", "two");
        tm.put("fox", "three");
        tm.put("jumps", "four");
        tm.put("over", "five");
        tm.put("the", "six");
        tm.put("lazy", "seven");
        tm.put("dog", "eight");
        for (String s : new String[] {
            "quick", "brown", "fox", "jumps", "over",
            "the", "lazy", "dog", "before", "way_after"}
        ) {
            if (tm.containsKey(s)) {
                // Here is the operation you are looking for.
                // It does not work for items not in the dictionary.
                int pos = tm.headMap(s).size();
                System.out.println("Key '"+s+"' is at the position "+pos);
            } else {
                System.out.println("Key '"+s+"' is not found");
            }
        }
    }
}

以下是程序生成的输出：

Key 'quick' is at the position 6
Key 'brown' is at the position 0
Key 'fox' is at the position 2
Key 'jumps' is at the position 3
Key 'over' is at the position 5
Key 'the' is at the position 7
Key 'lazy' is at the position 4
Key 'dog' is at the position 1
Key 'before' is not found
Key 'way_after' is not found