кластерные строки - какой алгоритм подходит?

Question

У меня есть несколько строк, и символы не будут повторяться в одной строке. например: «AABC» невозможно.

Я хочу сгруппировать их в множествами своими общими подстроками. например: «ABC, CDF, GHP» будет кластеризоваться в два набора {ABC, CDF}, {GHP}.

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

например: 1. «ABC, AHD, AKJ, LAN, WER» будет состоять из двух наборов {ABC, AHD, AKJ, LAN}, {WER}. 2. «ABC, BDF, HLK, YHT, PX» будет 3 набора {ABC, BDF}. {HLK, YHT}, {PX}.

Нахождение струны, которая не имеет ничего общего с другими, легко, я думаю;

for(i=0; i< strings.num; i++) 
{ str1 = strings[i]; 
    bool m_com=false; 
    for(j=0;j < strings.num; j++) 
    { 
     str2=strings[j]; 
     if(hascommon(str1,str2)) 
     m_com=true; 
    } 
    if(!m_com) 
    { 
    str1 has no common substring with any string, 
    } 
} 

сейчас я думаю о других, как их классифицировать, есть ли подходящий для этого алгоритм?

Input: строки (символы не будут повторяться)

выход: наборов (сохранить количество наборов как можно меньше)

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

пока я ищу хорошие способы сделать это, я также ценю предложения от других.

Совет: на самом деле эти строки являются простыми путями между двумя точками графика. Я хочу найти край, удаление которого разрешает все эти пути. число таких ребер должно быть минимальным. поэтому для AB, BC, CD это означает, что существует единственный путь ABCD. и я записываю алгоритм поиска общих подстрок в моем случае (мой случай намного проще). Я думаю, что я мог бы использовать этот алгоритм во время кластеризации для измерения сходства.

Возможно, у меня есть два пути, {ABC, ADC}, оба удаления A или удаления B могут разделить пути. , или я мог бы иметь {ABC, ADC, HG}, поэтому все действия удаляются {A, H} или {CH}, {CG} или {AG}.

Я думал, что смогу это решить, найдя общие подстроки, затем я решаю, где удалить края.

Answer 1

Вы должны использовать алгоритм кучного для вашей работы, чтобы создать перестановкам https://en.wikipedia.org/wiki/Heap «s_algorithm

Answer 2

Одно следует отметить первый:

For any two strings, "having common substring" is really equivalent to "having common letter". Thus we can replace the condition by "having common letter".

Рассмотрим граф G, вершинами которого являются строки, и две строки связаны ребром тогда и только тогда, когда они имеют общую букву. Тогда вы действительно просите разделить график G на подключенные компоненты. Это можно сделать легко, используя стандартные алгоритмы работы с графами, c.f. the wiki page here.

Остается задача установить график. Это также легко: во-первых, создайте 26 ящиков с пометкой A до Z и прочитайте каждую строку один раз. Если строка содержит букву A, тогда поместите ее (или ее индекс) в поле A и т. Д. Наконец, эти строки внутри одной коробки имеют грани, соединяющие друг с другом.

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

Answer 3

В отличие от WhatsUp, я предполагаю, что вы хотите, чтобы любые две строки в подмножестве имели общую подстроку. Это означает, что для AB, BC, CD, {AB, BC, CD} недействительным решением, потому что AB и CD не имеют общей подстроки.

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

Если мы не принимаем цепочки (как описано в начале), проблема становится нахождение minimum clique cover, что, к сожалению, является NP-полным.