Свертывание набора строк на основе заданного расстояния Хэмминга

Question

С учетом набора строк (первый столбец) и количества (второй столбец), например:

aaaa 10
aaab 5
abbb 3
cbbb 2
dbbb 1
cccc 8

Существуют ли какие-либо алгоритмы или даже реализации (в идеале как руководитель Unix, R или python), которыесвернуть этот набор в новый набор на основе заданного расстояния Хэмминга.

• Свертывание подразумевает добавление счетчика
• Строки с меньшим количеством свернуты в строки с большим числом.

Например, скажем, для расстояния Хэмминга 1, вышеприведенный набор свернет вторую строку aaab в aaaa, так как они на расстоянии 1 Хэмминга друг от друга и aaaa имеет большее число. Свернутая запись будет иметь объединенное количество, здесь aaaa 15

Поэтому для этого набора мы получим следующий свернутый набор:

aaaa 15
abbb 6
cccc 8

В идеале реализация должна бытьэффективен, поэтому приветствуется даже эвристика, которая не гарантирует оптимального решения.

Дальнейшие знания и мотивация

Вычисление расстояния Хэмминга между 2 строками (парой) реализовано в большинстве языков программирования,Решение грубой силы вычислило бы вычисление расстояния между всеми парами. Может быть, нет никакого способа обойти это. Однако, например, я бы предположил, что эффективные решения позволят избежать вычисления расстояния для всех пар и т. Д. Есть, возможно, умные способы сохранить некоторые вычисления, основанные на теории метрик (поскольку расстояние Хэмминга является метрикой), например, если расстояние Хэмминга между x и z равно3, а x и y равно 3, я могу избежать вычисления между y и z. Возможно, есть разумный подход k-mer, или, может быть, какое-то эффективное решение для постоянного расстояния (скажем, d=1).

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

Answer 1

Я придумал следующее:

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

Я предлагаю использовать дерево точек обзора в качестве метрического индекса.

Алгоритм будет выглядеть следующим образом:

1. построение метрического индекса из строк и их оценок
2. построение максимальной кучи из строк и их оценок
3. для строки с наивысшей оценкой в ​​максимальной куче:
4. использовать метрический индекс для поиска ближайших строк
5. напечатать строку, а сумму ее оценки и ближайших строк
6. удалить из метрического индекса строку и каждый изстроки рядом с
7. удалить из максимальной кучи строку и каждую из строк рядом с
8. повторять 3-7, пока максимальная куча не станет пустой

Возможно, этоможно упростить, используя использованную таблицу, а не удаляя что-либо. Для индекса метрического пространства не требуется эффективного удаления, а максимальная куча не должна поддерживать удаление по значению. Но это было бы медленнее, если окрестности большие и часто перекрываются. Поэтому эффективное удаление может оказаться необходимой трудностью.

1. построить индекс метрики из строк и их оценок
2. построить максимальную кучу из строк и их оценок
3. создайте используемую таблицу из пустого набора
4. для строки с наибольшим счетом в максимальной куче:
5. , если эта строка находится в используемой таблице: начните заново со следующей строки
6. используйте метрический индекс, чтобы найти строки рядом:
7. удалить все строки рядом, которые есть в используемой таблице.
8. вывести строку, а также сумму ее оценки и ее значения рядом. строки
9. добавить строки рядом с используемой таблицей
10. повторять 4-9, пока максимальная куча не станет пустой

Я не могу предоставить анализ сложности.

Я думал о втором алгоритме. Часть, которую я думал, была медленной, была проверка соседства с использованным столом. В этом нет необходимости, поскольку удаление из дерева точек обзора может быть выполнено за линейное время. При поиске соседей, помните, где они были найдены, а затем удалите их позже, используя эти места. Если в качестве точки наблюдения используется сосед, пометьте его как удаленный, чтобы поиск не возвращал его, а оставил бы его в покое в противном случае. Я думаю, что это восстанавливает его ниже квадратичного. В противном случае это будет что-то вроде количества предметов, умноженного на размер окрестности.

---

В ответ на комментарий. Проблема заключалась в том, что «строки с меньшим числом свернуты в строки с большим числом». как таковой, он вычисляет это. Это не жадное приближение, которое может привести к неоптимальному результату, так как нечего было максимизировать или минимизировать. Это точный алгоритм. Возвращает предмет с наивысшей оценкой в ​​сочетании с оценкой соседства.

Это можно рассматривать как назначение лидера каждому району так, чтобы у каждого предмета было не более одного лидера, и этот лидер имел наибольший общий результат. Это можно рассматривать как ориентированный граф.

Спецификация не предназначена для задач динамического программирования или оптимизации. Для этого вы бы попросили предмет с наибольшим количеством баллов в районе наибольшего общего выигрыша. Это также можно решить аналогичным образом, изменив строки функции ранжирования от ее оценки до пары суммы ее оценки и ее окрестности, и ее оценки.

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