Как эффективно рассчитать коэффициент кости между 900 000 строк?

Question

У меня есть корпус из 900 000 строк. Они различаются по длине, но в среднем насчитывают около 4500 символов. Мне нужно найти наиболее эффективный способ вычисления коэффициента кости каждой строки, так как он относится к любой другой строке. К сожалению, это приводит к тому, что алгоритм коэффициента Кости используется около 810 000 000 000 раз.

Каков наилучший способ структурировать эту программу для повышения эффективности? Очевидно, что я могу предотвратить вычисление игральных костей секций A и B, а затем B и A - но это только вдвое меньше требуемой работы. Должен ли я рассмотреть возможность использования некоторых ярлыков или создания какого-то бинарного дерева?

Я использую следующую реализацию алгоритма коэффициента Кости в Java:

public static double diceCoefficient(String s1, String s2) {
    Set<String> nx = new HashSet<String>();
    Set<String> ny = new HashSet<String>();

    for (int i = 0; i < s1.length() - 1; i++) {
        char x1 = s1.charAt(i);
        char x2 = s1.charAt(i + 1);
        String tmp = "" + x1 + x2;
        nx.add(tmp);
    }
    for (int j = 0; j < s2.length() - 1; j++) {
        char y1 = s2.charAt(j);
        char y2 = s2.charAt(j + 1);
        String tmp = "" + y1 + y2;
        ny.add(tmp);
    }

    Set<String> intersection = new HashSet<String>(nx);
    intersection.retainAll(ny);
    double totcombigrams = intersection.size();

    return (2 * totcombigrams) / (nx.size() + ny.size());
}

Моя конечная цель - вывести идентификатор для каждого раздела, у которого коэффициент кости больше 0,9, с другим разделом.

Спасибо за любой совет, который вы можете дать!

Answer 1

Сделайте один проход по всем строкам и создайте HashMap, который отображает каждый биграмм на набор индексов строк, содержащих этот биграмм. (В настоящее время вы создаете биграмный набор 900 000 раз для каждой строки.)

Затем выполните обход всех наборов и постройте HashMap из пар [index, index] для общего числа биграмм. (Последняя карта не должна содержать избыточных пар ключей, таких как [1,2] и [2,1] - просто храните одну или другую.)

Оба эти этапа можно легко распараллелить. Если вам нужен пример кода, пожалуйста, дайте мне знать.

ПРИМЕЧАНИЕ одна вещь, хотя: из 26 букв английского алфавита можно получить в общей сложности 26x26 = 676 биграмм. Многие из них никогда не будут или почти никогда не будут найдены, потому что они не соответствуют правилам английского правописания. Поскольку вы создаете наборов биграмм для каждой строки, а строки такие длинные, вы, вероятно, найдете почти одинаковые биграммы в каждой строке. Если бы вы собирали списки биграмм для каждой строки (другими словами, если бы частота каждой биграммы считалась), более вероятно, что вы действительно сможете измерить степень схожести между строками, но тогда вычисление коэффициента Дайса, приведенное в статье в Википедии, не сработает; вам нужно будет найти новую формулу.

Я предлагаю вам продолжить исследование алгоритмов определения сходства между строками, попробовать реализовать несколько из них и запустить их на меньшем наборе строк, чтобы увидеть, насколько хорошо они работают.

Answer 2

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

1) Не создавайте свои HashSets каждый раз, когда вы делаете вызов diceCoefficient ()! Это должно значительно ускорить процесс, если вы просто сделаете это один раз для каждой строки и сохраните результат.

2) Поскольку вам важно только, если конкретный биграмм присутствует в строке, вы можете использовать битовый набор с битом для каждого возможного биграмма, а не полный HashMap. Расчет коэффициента затем будет упрощен до двух наборов битов AND и подсчета количества установленных битов в результате.

3) Или, если у вас есть огромное количество возможных биграмм (возможно, Unicode?) - или монотонных строк, содержащих только несколько биграмм - отсортированный массив биграмм может обеспечить более быстрое и более эффективное сравнение пространства. 1011 *

Answer 3

Их кодировка как-то ограничена? Если это так, вы можете вычислить количество символов по их коду в каждой строке и сравнить эти числа. После такого предварительного вычисления (оно будет занимать 2 * 900K * S байт памяти [если мы предположим, что в одной и той же строке не будет найдено символов более чем 65K раз), где S - другое количество символов) Тогда вычисление коэффициента заняло бы O (S) время. Конечно, это было бы полезно, если S <4500. </p>

Answer 4

Вы должны придумать какое-то неравенство, например: D (X1, X2)> 1-p, D (X1, X3) <1-q и p D (X2, X3) <1-q + p. Или что-то типа того. Теперь, если 1-q + p <0,9, то, вероятно, вам не нужно оценивать D (X2, X3). </p>

PS: я не уверен насчет этого точного неравенства, но у меня есть внутреннее чувство, что это может быть правильно (но у меня нет достаточно времени, чтобы фактически сделать выводы сейчас). Посмотрите на некоторые из неравенств с другими мерами сходства и посмотрите, являются ли какие-либо из них действительными для коэффициента Кости.

=== Также ===

Если в наборе A есть элементы, и если ваш порог равен r (= 0,9), то в наборе B должно быть количество элементов b, которое должно быть таким, чтобы: r * a / (2-r) <= b < = (2-р) * а / р. Это должно устранить необходимость много сравнений ИМХО. Вероятно, вы можете отсортировать строки по длине и использовать окно, описанное выше, чтобы ограничить сравнения. </p>