在Java TreeMap中查找元素位置

Question

我正在使用字符串的TreeMap TreeMap<String, String>,并使用它来实现单词的Dictionay.

然后我有一个文件集合,并希望在字典定义的向量空间(单词空格)中创建每个文件的表示.

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

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

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

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

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

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

2)TreeMap上是否有一个迭代器(它按字母顺序排列),我可以获得它的位置？

3)最终我应该使用另一个类来实现字典？(如果你认为使用TreeMaps我不能做我需要的)如果是的话,哪个？

提前致谢.

增加部分:

由dasblinkenlight提出的解决方案看起来很好,但是存在复杂性问题(由于将密钥复制到数组中而与字典的维度呈线性关系),并且不能接受为每个文件执行此操作的想法.

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

Answer 1

构建树形图后,将其排序的密钥复制到一个数组中,并用于Arrays.binarySearch在O(logN)时间内查找索引.如果您需要该值,也可以在原始地图上查找.

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

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

Answer 2

另一种解决方案是使用TreeMap的headMap方法。如果该词存在于 中TreeMap，则size()其头部映射的 等于该词在字典中的索引。与我的其他答案相比，通过，这可能有点浪费。

以下是您在 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

Answer 3

我要感谢你们所有人为回答我的问题所付出的努力，他们都非常有用，并且充分利用他们每个人的优点，使我找到了我在项目中实际实施的解决方案。

我认为对我的单一问题的最佳答案是：

2）TreeMaps 上没有定义迭代器，如 @Isoliveira 所说：

There's no such implementation in the JDK itself. 
Although TreeMap iterates in natural key ordering,
its internal data structures are all based on trees and not arrays
(remember that Maps do not order keys, by definition, 
in spite of that the very common use case).

正如我在这个 SO 答案中发现的那样How to iterate over a TreeMap? ，迭代 a 中元素的唯一方法Map是使用map.entrySet()定义在Set（或具有迭代器的其他类）上的迭代器。

3) 可以使用 aTreeMap来实现字典，但这将保证查找所包含单词的索引时的复杂度为 O(logN)（在树数据结构中查找的成本）。

使用HashMap相同过程的复杂度将是 O(1)。

1）不存在这样的方法。唯一的解决办法就是彻底实施它。

正如@Paul所说

Assumes that once getPosition() has been called, the dictionary is not changed.

解决方案的假设是，一旦创建了字典，之后就不会更改：这样单词的位置将始终相同。

给出这个假设，我找到了一个解决方案，允许构建复杂度为 O(N) 的字典，并保证在查找中获得包含 constat 时间 O(1) 的单词索引的可能性。

我将字典定义为HashMap这样的：

public HashMap<String, WordStruct> dictionary = new HashMap<String, WordStruct>();

• key -->String代表字典中包含的单词
• value -->Object创建类的一个WordStruct

其中WordStruct类定义如下：

public class WordStruct {

    private int DictionaryPosition;    // defines the position of word in dictionary once it is alphabetically ordered

    public WordStruct(){

    }

    public SetWordPosition(int pos){
        this.DictionaryPosition = pos;
    }

}

并允许我记住任何我喜欢与词典中的词条相结合的属性。

现在，我填充字典，迭代我集合的所有文件中包含的所有单词：

THE FOLLOWING IS PSEUDOCODE

for(int i = 0; i < number_of_files ; i++){

        get_file(i);

        while (file_contais_words){

            dictionary.put( word(j) , new LemmaStruct());

        }

}   

一旦 HashMap 以任何顺序填充，我就会使用 @dasblinkenlight 指示的过程来一次性排序它，复杂度为 O(N)

    Object[] dictionaryArray = dictionary.keySet().toArray();
    Arrays.sort(dictionaryArray);

    for(int i = 0; i < dictionaryArray.length; i++){

        String word = (String) dictionaryArray[i];
        dictionary.get(word).SetWordPosition(i);

    }

从现在开始，要在字典中按单词的字母顺序排列索引位置，唯一需要做的就是访问它的变量DictionaryPosition：

因为单词知道您只需要访问它，并且这在HashMap.

再次感谢，祝大家圣诞快乐！