java

Question

我有一个 Tweet 对象列表（自制 class），我想删除 NEARLY 基于它们的重复项文本，使用 Levenshtein 距离。我已经通过散列推文的文本删除了相同的重复项，但现在我想删除相同但具有 最多 2-3 个不同字符 的文本。由于这是一种 O(n^2) 方法，我必须检查每条推文文本以及所有其他可用的文本。到目前为止，这是我的代码：

int distance;
for(Tweet tweet : this.tweets) {
     distance = 0;
     Iterator<Tweet> iter = this.tweets.iterator();
     while(iter.hasNext()) {
         Tweet currentTweet = iter.next();
         distance = Levenshtein.distance(tweet.getText(), currentTweet.getText());
         if(distance < 3 && (tweet.getID() != currentTweet.getID())) {
             iter.remove();
         }
     }
}

第一个问题是代码在某个时候抛出 ConcurrentModificationException 并且永远不会完成。第二个：我能做比这个双循环更好的事情吗？推文列表包含近 400.000 条推文，因此我们正在谈论 1600 亿次迭代！

Answer 1

此解决方案适用于手头的问题（目前已使用可能的输入进行测试），但如果您不实施与 return 1,0 和-1.

为什么不使用只能具有不同值的 Set 来实现自己的比较操作。它将是 O(n log(n)).

Set set = new TreeSet(new Comparator() {
            @Override
            public int compare(Tweet first, Tweet second) {
                int distance = Levenshtein.distance(first.getText(), second.getText());
                if(distance < 3){
                    return 0;
                }
                return 1;
            }
        });
        set.addAll(this.tweets);
        this.tweets = new ArrayList<Tweet>(set);

Answer 2

至于 ConcurrentModificationException: 正如其他人指出的那样，我正在从列表中删除元素，我也在外部for-each。将 for-each 更改为 normal for 解决了问题。

至于 O(n^2) 方法： 没有 "better" 算法比 O(n^2) 方法复杂。我想要做的是 "all-to-all" 比较以找到几乎重复的元素。当然有降低总容量的优化n，并发并行解析原始列表的子列表，但复杂度始终是二次方。

java - 从列表中删除几乎重复的内容

java - Remove nearly duplicates from a List

duplicates

levenshtein-distance

concurrentmodification