Сортировка строк так, чтобы расстояние Хемминга было низким между соседними строками - PullRequest
Новая
       16

Сортировка строк так, чтобы расстояние Хемминга было низким между соседними строками

10 голосов
/ 28 декабря 2011

Проблема:

У меня есть N (~ 100k-1m) строк, каждая длиной в D (например, 2000) и с низким алфавитом (например, 3 возможных символа). Я хотел бы отсортировать эти строки так, чтобы между смежными строками было как можно меньше изменений (например, расстояние Хэмминга мало). Решение не должно быть наилучшим, но чем ближе, тем лучше.

Пример

* * 1010

Мысли о проблеме

У меня плохое предчувствие, что это нетривиальная проблема. Если мы рассматриваем каждую строку как узел, а расстояния до других строк как ребро, то мы смотрим на проблему коммивояжера. Большое количество строк означает, что предварительный расчет всех парных расстояний потенциально невозможен, я думаю, что превращение проблемы в нечто большее, например Canadian Traveller Problem .

В настоящее время мое решение заключается в использовании дерева VP , чтобы найти жадное решение типа ближайшего соседа для задачи 

curr_string = a randomly chosen string from full set
while(tree not empty)
    found_string = find nearest string in tree
    tree.remove(found_string)
    sorted_list.add(curr_string)
    curr_string = found_string

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

Ответы [ 2 ]

2 голосов
/ 05 января 2012

Даже если вы считаете эту проблему похожей на задачу коммивояжера (TSP), я считаю, что расстояния Хэмминга будут следовать неравенству треугольника (Хэмминга (A, B) + Хемминга (B, C) ≤ Хемминга (A, C) )), так что вы действительно имеете дело только с ∆TSP (метрическая задача коммивояжера), для которой существует ряд алгоритмов, дающих хорошие приближения при идеальном результате. В частности, алгоритм Christofides всегда будет давать вам путь не более чем в 1,5 раза меньше минимально возможной длины.

1 голос
/ 05 января 2012

Да, это проблема коммивояжера , но я не знаю, может ли какая-либо из дюжины программ из библиотеки исходного кода TSP набрать 1 млн. Очков прямо с помощью штекера-в метрике.

Возможный двухэтапный подход:

1) разбить 1M точек на 50 кластеров с помощью Поиск ближайшего соседа .Сделайте TSP на 50 кластерных центрах.

2) поместите все 1M - 50 точек между 2 ближайшими центрами;сделайте TSP для каждой строки 1M / 50. Здесь «50» может быть 100 или 1000. Если 1000 слишком велико, рекурсивно: разделите 1000 на 30 кластеров по ~ 30 в каждом.

K-means может кластеризовать 1Mочков, но опять же я не знаю о быстрой реализации с плагином метрики.Однако см. scikit-Learn кластеризация

Чтобы найти центроид из N точек, один из которых минимизирует | центр - все остальные |, вы можете одержать победу над O (N ^ 2), только взявлучший из случайной выборки скажем, sqrt (N) - должно быть достаточно хорошо.(Или гуглите / задайте отдельный вопрос на быстром приближенном центроиде). ​​

Сначала плотно упакуйте данные, чтобы сохранить доступ к памяти во всем потоке.В этом случае закодируйте abc как 00 01 10 (расстояние Хэмминга между каждой парой = 1): 2000 x 2 бита = 500 байтов.Кстати, поиск минимального Hammingdist (4 Кбит, 10 К x 4 К) занимает ~ 40 мсек на моем компьютере Mac.

...