Алгоритм группировки похожих строк для поиска дубликатов

Есть функция по удалению дубликатов строк, которая работает по следующему алгоритму. Подготовка строк: очистка от спец символов, пробелов, нижний регистр, разделение на шинглы (n-граммы). Во время подготовки строки добавляются в набор Set. Если набор не разрешил добавление, найден точный дубликат (полное равенство строк abc == abc). В результате получаем набор строк, из которых удалены полные дубли. Следующий этап это поиск похожих строк с помощью Dice-коэффициента. Если коэффициент больше заданного значения (0.84), строки считаются дублями.

Проблема в количестве итераций при сравнении коэффициентов. Худший вариант это сравнение каждого с каждым. Существенный прирост появляется, если предварительно сгруппировать строки по первому шинглу. Например, среди 10 тысяч строк только 300 начинаются с "ma". Тогда они сравниваются только друг с другом. Соответственно минус такого ускорения в том, что схожие строки с разным написанием первого шингла никогда не встретятся.

Строки всегда короткие. К примеру, "исполнитель название трека". Как правило исполнитель не содержит ошибки в первом шингле, но такое возможно для менее популярных или для названий из файлов.

skillet hero
sillet hero remix
pvris monster
awolnation sail
awolantion sail cover
...

Есть ли алгоритм группировки схожих коротких строк? Не просто по первому шингу. Приоритет больше на скорость, чем потребление памяти. Пробовал по этому описанию реализовать LSH, но оно считает существенно дольше, чем просто прямой перебор. И везде сопровождается описанием, что предназначен для сравнения целых документов, а не коротких строк.

fun List<IExecutorItem>.deduplicate(model: DeduplicatorModel): List<IExecutorItem> {
    val shingleSize = 2
    val baskets = mutableMapOf<String, MutableSet<Ngrams>>()
    val comparableItems = linkedMapOf<IExecutorItem, MutableSet<Ngrams>>()
    val comparableNames = mutableSetOf<String>()

    this.forEach { item ->
        item.getCleanNames(model.targetEntityType, false).forEach { name ->
            if (comparableNames.add(name)) {
                val iSet = DiceCoefficient.splitToNgrams(name, shingleSize)
                comparableItems.getOrPut(item) { mutableSetOf() }.run { add(iSet) }
                baskets.getOrPut(iSet.map.keys.first()) { mutableSetOf() }.run { add(iSet) }
            }
        }
    }

    return comparableItems.entries.fold(mutableListOf()) { acc, (item, shingles) ->
        shingles.forEach { iSet ->
            baskets[iSet.map.keys.first()]?.forEach { jSet ->
                if (iSet == jSet || !DiceCoefficient.isDuplicate(iSet, jSet, model.minDice)) {
                    acc.add(item)
                    return@fold acc
                }
            }
        }
        return@fold acc
    }
}

data class Ngrams(
    val map: LinkedHashMap<String, Int>,
    val maxIntersection: Int,
)

object DiceCoefficient {

    const val DEFAULT_DICE_THRESHOLD = 0.84

    fun splitToNgrams(list: List<String>, gramSize: Int): List<Ngrams> {
        return list.map { splitToNgrams(it, gramSize) }
    }

    fun splitToNgrams(text: String, gramSize: Int): Ngrams {
        val cleanString = text.replace("""\s""".toRegex(), "")
        val items = linkedMapOf<String, Int>()
        for (i in 0 until cleanString.length - gramSize + 1) {
            val ngram = cleanString.substring(i, i + gramSize)
            items[ngram] = items[ngram]?.plus(1) ?: 1
        }
        return Ngrams(items, items.values.sum())
    }

    fun isDuplicate(x: Ngrams, y: Ngrams, threshold: Double): Boolean {
        val minIntersection = (threshold * (x.map.size + y.map.size)) / 2.0
        if (x.maxIntersection < minIntersection || y.maxIntersection < minIntersection) {
            return false
        }

        var intersection = 0
        var yLeftNrams = y.maxIntersection
        val xNgramMap = HashMap(x.map)
        for (yNgram in y.map.keys) {
            val count = xNgramMap[yNgram] ?: 0
            if (count > 0) {
                intersection += 1
                if (intersection >= minIntersection) {
                    return true
                }
                xNgramMap[yNgram] = count - 1
            }
            yLeftNrams -= 1
            if (yLeftNrams < (minIntersection - intersection)){
                return false
            }
        }
        return false
    }
}