java-удаление почти дубликатов из списка

У меня есть список объектов Tweet (homegrown class), и я хочу удалить его. почти что дубликаты, основанные на их тексте, с использованием расстояния Левенштейна. Я уже удалил идентичные дубликаты, хешируя тексты твитов, но теперь я хочу удалить тексты, которые идентичны, но имеют до 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 твитов, так что речь идет о 160 миллиардах итераций!

2 2
duplicates concurrentmodification levenshtein-distance

2 ответа:

Это решение работает для рассматриваемого вопроса(до сих пор тестировалось с возможными входными данными), но обычные операции набора для удаления дубликатов не будут работать, если вы не реализуете полный контракт для сравнения, чтобы вернуть 1,0 и -1.

Почему бы вам не реализовать свою собственную операцию сравнения, используя набор, который может иметь только различные значения. Это будет 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);
-1

Что касается исключения ConcurrentModificationException: как указывали другие,я удалял элементы из списка, который я также повторял во внешнем для каждого. Изменение для-каждого в нормальное для решило проблему.

Что касается подхода O(n^2): нет "лучшего" алгоритма в отношении его сложности, чем подход O(n^2). То, что я пытаюсь сделать,-это сравнение "все ко всем", чтобы найти почти повторяющиеся элементы. Конечно, есть оптимизации, чтобы понизьте общую емкость n, распараллеливание для одновременного разбора вложенных списков исходного списка, но сложность квадратична во все времена.

-1