Вопрос:

Алгоритм для нахождения всех общих подстрок любой длины между 2 строками, а затем подсчета вхождений в строке 2?

c string algorithm tree nodes

1371 просмотра

4 ответа

232 Репутация автора

Я столкнулся с необычным испытанием и пока не могу определить наиболее эффективный алгоритм для этого.


Используя в качестве примера следующие 2 строки, найдите все общедоступные подстроки между 2 строками любой длины и посчитайте количество вхождений всех этих общих подстрок в строке 2. Ваш алгоритм также должен иметь возможность вычислять общие подстроки между файлы, содержащие строки размером до 100 МБ или более.

Пример:

Строка 1: ABCDE512ABC361EG51D

Строка 2: ADE5AHDW4131EG1DG5C

Учитывая эти 2 строки, этот алгоритм найдет следующие общие подстроки: A, C, D, E, 5,1,3, G, DE, E5, EG, G5,1D, DE5,1EG

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

A: 2 вхождения в строке 2

C: 1 вхождение в строке 2

D: 3 вхождения в строке 2

и т.д..


Первый подход, который я использовал, чтобы обойти эту проблему, был грубым форсированием моего пути вычисления общих разделяемых подстрок с использованием двух вложенных циклов - очевидно, наименее эффективный, но это был быстрый и грязный способ понять, какие ожидаемые результаты должно быть с меньшим тестовым вводом и самым медленным возможным временем выполнения, которое составляло около 2 минут для вычисления всех общих общих подстрок между двумя файлами, содержащими строки ascii размером 50 КБ. Увеличение размера до 1 МБ привело к тому, что это прекратилось из-за огромного количества общих вложенных итераций, которые должны были произойти, чтобы вычислить это.

Следующим подходом было использование деревьев - просмотр количества памяти, которое я мог обменять, чтобы оптимизировать время вычислений. Этот подход был намного быстрее. Те же два файла по 50 КБ, которые занимали 2 минуты методом грубой силы, были почти мгновенными. Работа с файлами размером 1 МБ была слишком быстрой (секунды), но, продолжая тестировать файлы большего и большего размеров, я быстро столкнулся с проблемами памяти из-за размеров дерева.


Примечание. Строковые файлы будут содержать только символы ASCII!


Редактировать:

Я обостряю это немного дальше, пожалуйста, смотрите:

https://gist.github.com/braydo25/f7a9ce7ce7ad7c5fb11ec511887789bc

Автор: Braydon Batungbacal Источник Размещён: 04.11.2016 10:39

Ответы (4)


9 плюса

27934 Репутация автора

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

struct Occurrence
{
    //The vectors contain indices to the first character of the occurrence in ...
    std::vector<size_t> s1;  // ... string 1 and ...
    std::vector<size_t> s2;  // ... string 2.
};

int main()
{
    //If you cannot load the entire strings in memory, a memory-mapped file might be
    //worth considering
    std::string s1 = "ABCDE512ABC361EG51D";
    std::string s2 = "ADE5AHDW4131EG1DG5C";

    //These vectors store the occurrences of substrings for the current and next length
    std::vector<Occurrence> occurrences, nextOccurrences;
    int length = 1;

    std::map<char, Occurrence> occurrenceMap;
    //Initialize occurrences
    for (int i = 0; i < s1.length(); ++i)
        occurrenceMap[s1[i]].s1.push_back(i);
    for (int i = 0; i < s2.length(); ++i)
        occurrenceMap[s2[i]].s2.push_back(i);

    for (auto& pair : occurrenceMap)
    {
        if (pair.second.s1.size() > 0 && pair.second.s2.size() > 0)
            occurrences.push_back(std::move(pair.second));
    }

    do
    {
        nextOccurrences.clear();

        std::cout << "Length " << length << std::endl;
        for(auto& o : occurrences)
        {
            std::cout << std::string(s1.c_str() + o.s1[0], length) << " occurred "
                      << o.s1.size() << " / " << o.s2.size() << " times." << std::endl;

            //Expand the occurrence
            occurrenceMap.clear();
            for (auto p : o.s1)
            {
                if (p + length < s1.length())
                    occurrenceMap[s1[p + length]].s1.push_back(p);
            }                   
            for (auto p : o.s2)
            {
                if (p + length < s2.length())
                occurrenceMap[s2[p + length]].s2.push_back(p);
            }
            for (auto& pair : occurrenceMap)
            {
                if (pair.second.s1.size() > 0 && pair.second.s2.size() > 0)
                    nextOccurrences.push_back(std::move(pair.second));
            }
        }

        ++length;
        std::swap(occurrences, nextOccurrences);

    } while (!occurrences.empty());


    return 0;
}

Выход:

Length 1
1 occurred 3 / 3 times.
3 occurred 1 / 1 times.
5 occurred 2 / 2 times.
A occurred 2 / 2 times.
C occurred 2 / 1 times.
D occurred 2 / 3 times.
E occurred 2 / 2 times.
G occurred 1 / 2 times.
Length 2
1D occurred 1 / 1 times.
1E occurred 1 / 1 times.
DE occurred 1 / 1 times.
E5 occurred 1 / 1 times.
EG occurred 1 / 1 times.
G5 occurred 1 / 1 times.
Length 3
1EG occurred 1 / 1 times.
DE5 occurred 1 / 1 times.

Большая часть памяти будет использоваться во время инициализации, поскольку для каждого символа обеих входных строк будет запись. Если вы знаете приблизительную длину строк, вы можете выбрать более подходящий тип данных индекса, чем size_t. Объем необходимой памяти находится в порядке размера ввода. Таким образом, два файла размером 100 МБ не должны быть проблемой для обычных компьютеров. После инициализации (точнее, после первой итерации цикла) большинство этих данных будут удалены, поскольку они больше не нужны.

Автор: Nico Schertler Размещён: 05.11.2016 03:28

1 плюс

5215 Репутация автора

Посмотрев на две строки и немного подумав об этом, я выполнил эту процедуру в своей голове, и теперь я собираюсь перевести ее на шаги.

String 1: ABCDE512ABC361EG51D  // S1
String 2: ADE5AHDW4131EG1DG5C  // S2

Когда я думал об этом, мы можем сравнивать символы и / или подстроки от S1 до S2, отслеживая вхождения.

S1[0] = 'A'  compare S2[0]  = 'A' = true : found A in S2 at location 0
S1[0] = 'A'  compare S2[1]  = 'D' = false
S1[0] = 'A'  compare S2[2]  = 'E' = false
S1[0] = 'A'  compare S2[3]  = '5' = false
S1[0] = 'A'  compare S2[4]  = 'A' = true : found A in S2 at location 4
S1[0] = 'A'  compare S2[5]  = 'H' = false
S1[0] = 'A'  compare S2[6]  = 'D' = false
S1[0] = 'A'  compare S2[7]  = 'W' = false
S1[0] = 'A'  compare S2[8]  = '4' = false
S1[0] = 'A'  compare S2[9]  = '1' = false
S1[0] = 'A'  compare S2[10] = '3' = false
S1[0] = 'A'  compare S2[11] = '1' = false; 
S1[0] = 'A'  compare S2[12] = 'E' = false; 
S1[0] = 'A'  compare S2[13] = 'G' = false;
S1[0] = 'A'  compare S2[14] = '1' = false;
S1[0] = 'A'  compare S2[15] = 'D' = false;
S1[0] = 'A'  compare S2[16] = 'G' = false;
S1[0] = 'A'  compare S2[17] = '5' = false;
S1[0] = 'A'  compare S2[18] = 'C' = false;

// End of First Search - Occurrences of 'A' in S2 is 2 at locations {0,4}

// Next Iteration
String 1: ABCDE512ABC361EG51D  // S1
String 2: ADE5AHDW4131EG1DG5C  // S2

// Repeat this for all single characters Of S1 against S2
'A' in S2 = 2  at {0,4}
'B' in S2 = 0 
'C' in S2 = 1  at {18}
'D' in S2 = 3  at {1,6,15}
'E' in S2 = 2  at {2,12}
'5' in S2 = 2  at {3,17}
'1' in S2 = 3  at {9,11,14}
'2' in S2 = 0
'A' Already Found Above Skip
'B' Already Found Above Skip
'C' Already Found Above Skip
'3' in S2 = 1  at {10}
'6' in S2 = 0
'1' Already Found Above Skip
'E' Already Found Above Skip
'G' in S2 = 2  at {13, 16}
'5' Already Found Above Skip
'1' Already Found Above Skip
'D' Already Found Above Skip

Это завершило бы первый набор итераций для выполнения всех отдельных символов, и, как вы можете видеть, мы также создали список и карту или наборы не только вхождений, но и их местоположений, и мы можем сохранить их для будущих ссылок. Поэтому, если мы начнем искать S1 [0 & 1] в S2, мы знаем, что S1 [1] не существует в S2, поэтому мы можем разорвать и нам не нужно идти по этой цепочке, и, поскольку мы можем вырваться из этой ветви мы также можем пропустить выполнение S1 [1 & ... N] и перейти непосредственно к S1 [2], и мы знаем, что существует только 1 вхождение S1 [2], которое является 'C' в S2, расположенном в {18}, что это конец строки, поэтому нет необходимости искать S1 [2 & ... N], поэтому мы можем пропустить это и перейти к S1 [3], который равен 'D', и мы знаем, что он существует в S2 в {1,6,15}, так что теперь мы можем начать наш поиск S1 [3 & ... N], начиная с S2 [1 & ... N] затем снова выполните тот же поиск S1 [3 & ... N], начиная с S2 [6 & ... N] и, наконец, снова начиная с S2 [15 & ... N], теперь мы нашли все подстроки, начинающиеся с D в S2, и мы можем сохранить их вхождения; однако это то, где мы хотим найти самую длинную подстроку между ними. Самая длинная подстрока - «DE5», и она встречается только в одном случае, но из этого мы также уже нашли подстроки «DE» и «E5», поэтому мы можем искать их и в этой точке, а затем находим что есть 1 вхождение каждого. И мы просто повторяем этот процесс. Сначала это займет довольно много времени, но чем больше вы будете проходить по строкам, тем быстрее это будет работать из-за устранения уже найденных вхождений, а также пропуска не найденных подстрок S1 в S2. N] затем снова выполните тот же поиск S1 [3 & ... N], начиная с S2 [6 & ... N] и, наконец, снова начиная с S2 [15 & ... N], теперь мы нашли все подстроки это начинается с D в S2, и мы можем сохранить их вхождения; однако это то, где мы хотим найти самую длинную подстроку между ними. Самая длинная подстрока - «DE5», и она встречается только в одном случае, но из этого мы также уже нашли подстроки «DE» и «E5», поэтому мы можем искать их и в этой точке, а затем находим что есть 1 вхождение каждого. И мы просто повторяем этот процесс. Сначала это займет довольно много времени, но чем больше вы будете проходить по строкам, тем быстрее это будет работать из-за устранения уже найденных вхождений, а также пропуска не найденных подстрок S1 в S2. N] затем снова выполните тот же поиск S1 [3 & ... N], начиная с S2 [6 & ... N] и, наконец, снова начиная с S2 [15 & ... N], теперь мы нашли все подстроки это начинается с D в S2, и мы можем сохранить их вхождения; однако это то, где мы хотим найти самую длинную подстроку между ними. Самая длинная подстрока - «DE5», и она встречается только в одном случае, но из этого мы также уже нашли подстроки «DE» и «E5», поэтому мы можем искать их и в этой точке, а затем находим что есть 1 вхождение каждого. И мы просто повторяем этот процесс. Сначала это займет довольно много времени, но чем больше вы будете проходить по строкам, тем быстрее это будет работать из-за устранения уже найденных вхождений, а также пропуска не найденных подстрок S1 в S2.

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

РЕДАКТИРОВАТЬ - Как спросили в комментариях о разнице между этим ответом и ответом другого человека, а также с учетом сложности времени и пространства, здесь приведена версия моего алгоритма, выполняющего первый проход, ища отдельные символы и создавая таблицы позиций, и существуют ли они во втором строка. Сохраненный вектор в классе содержит каждый уникальный символ в S1 в S2. Это может быть использовано для поиска более длинных подстрок.

// C++ - The user asked for this in C but I haven't used C in nearly 10 years so this is my version of it in C++ :( 
#include <string>
#include <vector>

class SubStringSearch {
private:
    std::string S1;
    std::string S2; 

    struct SubstringResult {
        std::string substring;
        bool found;
        std::vector<unsigned> positions;

        SubstringResult(){}
        SubstringResult( const std::string& substringIn, bool foundIn, std::vector<unsigned> positionsIn ) :
            substring( substringIn ), found( foundIn ), positions( positionsIn ) {}
    };

    std::vector<SubstringResult> results;

public:
    SubStringSearch( const std::string& s1, const std::string& s2 ) : S1( s1 ), S2( s2 ) {}

    void compareStringsFirstPass();
    std::vector<unsigned> findLocations( const std::string& str, char findIt );
    void printResults() const;

};

std::vector<unsigned> SubStringSearch::findLocations( const std::string& str, char findIt ) {
    std::vector<unsigned> locations;
    for ( unsigned i = 0; i < str.size(); ++i ) {
        if ( str[i] == findIt ) {
            locations.push_back( i );
        }
    }
    return locations;
}

void SubStringSearch::compareStringsFirstPass() {
    std::vector<unsigned> positions;
    std::string sub;
    bool alreadyFound = false;

    for ( unsigned idx = 0; idx < S1.size(); ++idx ) {
        sub = S1[idx];

        if ( idx > 0 ) {
            for ( unsigned u = 0; u < results.size(); ++u ) {
                if ( sub == results[u].substring ) {
                    alreadyFound = true;
                    break;
                }
            }
        }

        // Added An If Else Here To Reduce Unneeded Calls To findLocations()
        if ( alreadyFound ) {
            alreadyFound = false;
            continue;
        } else {
            positions = findLocations( S2, S1[idx] );
        }

        if ( positions.size() > 0 && !alreadyFound ) {
            results.push_back( SubstringResult( sub, true, positions ) );
        } else if ( !alreadyFound ) {
            positions.clear();
            results.push_back( SubstringResult( sub, false, positions ) );
        }

        positions.clear();
        alreadyFound = false;
    }
}

void SubStringSearch::printResults() const {
    for ( unsigned u = 0; u < results.size(); ++u ) {
        if ( results[u].found ) {
            std::cout << results[u].substring << " found in S2 at " << std::setw(2);
            for ( unsigned i = 0; i < results[u].positions.size(); ++i ) {
                std::cout << std::setw(2) << results[u].positions[i] << " ";
            }
            std::cout << std::endl;
        }
    }
}

int main() {
    std::string S1( "ABCDE512ABC361EG51D" );
    std::string S2( "ADE5AHDW4131EG1DG5C" );

    SubStringSearch searchStrings( S1, S2 );
    searchStrings.compareStringsFirstPass();

    std::cout << "break point";

    return 0;
} // main

Поместите точку останова в эту последнюю строку печати и перейдите в ваш отладчик для ваших локальных или ваших autos в MSVC или что-то эквивалентное для вашей версии вашего компилятора / отладчика и проверьте содержимое переменной члена класса, которая является std :: vector, и вы увидите символ из S1 и прикрепленный к нему будет флаг bool, если он найден или нет, а также std :: vector для каждой из позиций. Таким образом, если флаг равен false, то размер вектора должен быть 0, и наоборот, если размер вектора> 0, тогда флаг должен быть истинным; также размер вектора положений - это также количество или вхождения этого символа во 2-й строке, что делает это хорошим, потому что нам не нужно ничего вычислять, мы можем просто получить это из самого вектора.

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

Автор: Francis Cugler Размещён: 17.12.2016 10:22

4 плюса

40766 Репутация автора

Решение

Вот реализация C, основанная на обходе массива суффиксов конкатенации входов с помощью самого длинного массива общих префиксов. Вы можете заменить реализацию массива суффиксов класса программирования (O (n log ^ 2 n)) на реальную (O (n) или O (n log n)) для значительного улучшения производительности. (РЕДАКТИРОВАТЬ: сделал это, с некоторыми другими изменениями, отражающими новые требования автора: https://github.com/eisenstatdavid/commonsub .)

#include <inttypes.h>
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef int_fast32_t I32;

#define Constrain(expression) _Static_assert(expression, #expression)
Constrain(CHAR_BIT == 8);
#define InputMaxBytes 80000000
Constrain(InputMaxBytes <= (INT_LEAST32_MAX - 2) / 2);
#define MaxLen (2 * InputMaxBytes + 2)
Constrain(MaxLen <= INT_FAST32_MAX / 2);

static I32 Len;
static I32 Begin2;
static signed char Buf[MaxLen];
static int_least32_t SufArr[MaxLen];
static int_least32_t SufRank[MaxLen];
static int_least32_t NewRank[MaxLen];
static int_least32_t *const LongCommPre = NewRank;  // aliased to save space
static uint_least64_t Bitmap2[(MaxLen >> 6) + 1];
static int_least32_t SparseCount2[(MaxLen >> 6) + 1];
static int_least32_t *const Stack = SufRank;  // aliased to save space

static void Slurp(const char *filename) {
  FILE *stream = fopen(filename, "r");
  if (stream == NULL) goto fail;
  I32 n = fread(Buf + Len, sizeof *Buf, InputMaxBytes + 1, stream);
  if (ferror(stream)) goto fail;
  if (n > InputMaxBytes) {
    fprintf(stderr, "%s: file is too large; increase InputMaxBytes\n",
            filename);
    exit(EXIT_FAILURE);
  }
  for (I32 i = 0; i < n; i++) {
    if (Buf[Len + i] < 0) {
      fprintf(stderr,
              "%s: file contains non-ASCII byte at offset %" PRIdFAST32 "\n",
              filename, i);
      exit(EXIT_FAILURE);
    }
  }
  Len += n;
  if (fclose(stream) == EOF) goto fail;
  return;
fail:
  perror(filename);
  exit(EXIT_FAILURE);
}

static I32 Radix;

static int CompareRankPairs(const void *iPtr, const void *jPtr) {
  I32 i = *(const int_least32_t *)iPtr;
  I32 j = *(const int_least32_t *)jPtr;
  if (SufRank[i] < SufRank[j]) return -1;
  if (SufRank[i] > SufRank[j]) return 1;
  I32 iRank = i + Radix < Len ? SufRank[i + Radix] : -2;
  I32 jRank = j + Radix < Len ? SufRank[j + Radix] : -2;
  if (iRank < jRank) return -1;
  if (iRank > jRank) return 1;
  return 0;
}

static void BuildSuffixArray(void) {
  for (I32 i = 0; i < Len; i++) {
    SufArr[i] = i;
    SufRank[i] = Buf[i];
  }
  for (Radix = 1; true; Radix *= 2) {
    qsort(SufArr, Len, sizeof *SufArr, CompareRankPairs);
    NewRank[0] = 0;
    for (I32 i = 1; i < Len; i++) {
      NewRank[i] = CompareRankPairs(&SufArr[i - 1], &SufArr[i]) == 0
                       ? NewRank[i - 1]
                       : NewRank[i - 1] + 1;
    }
    for (I32 i = 0; i < Len; i++) {
      SufRank[SufArr[i]] = NewRank[i];
    }
    if (NewRank[Len - 1] == Len - 1) break;
  }

  I32 lenCommPre = 0;
  for (I32 i = 0; i < Len; i++) {
    if (SufRank[i] == Len - 1) {
      LongCommPre[SufRank[i]] = -1;
      continue;
    }
    while (Buf[i + lenCommPre] == Buf[SufArr[SufRank[i] + 1] + lenCommPre]) {
      lenCommPre++;
    }
    LongCommPre[SufRank[i]] = lenCommPre;
    if (lenCommPre > 0) lenCommPre--;
  }
}

static I32 PopCount(uint_fast64_t x) {
  I32 v = 0;
  while (x != 0) {
    x &= x - 1;
    v++;
  }
  return v;
}

static void BuildCumCount2(void) {
  for (I32 i = 0; i < Len; i++) {
    if (SufArr[i] >= Begin2) {
      Bitmap2[i >> 6] |= UINT64_C(1) << (i & 63);
      SparseCount2[i >> 6]++;
    }
  }
  for (I32 i = 0; i < (Len >> 6); i++) {
    SparseCount2[i + 1] += SparseCount2[i];
  }
}

static I32 CumCount2(I32 i) {
  return SparseCount2[i >> 6] - PopCount(Bitmap2[i >> 6] >> (i & 63));
}

static void FindCommonStrings(void) {
  I32 lenCommPre = -1;
  for (I32 i = 0; i < Len; i++) {
    while (lenCommPre > LongCommPre[i]) {
      I32 begin = Stack[lenCommPre];
      I32 end = i + 1;
      I32 count2 = CumCount2(end) - CumCount2(begin);
      if (count2 > 0 && count2 < end - begin && lenCommPre > 0) {
        printf("%" PRIdFAST32 "\t%.*s\n", count2, (int)lenCommPre,
               Buf + SufArr[begin]);
      }
      lenCommPre--;
    }
    while (lenCommPre < LongCommPre[i]) {
      lenCommPre++;
      Stack[lenCommPre] = i;
    }
  }
}

int main(int argc, char *argv[]) {
  if (argc != 3) {
    fputs("usage: commonsub needle haystack\n", stderr);
    exit(EXIT_FAILURE);
  }
  Len = 0;
  Slurp(argv[1]);
  Buf[Len] = -1;
  Len++;
  Begin2 = Len;
  Slurp(argv[2]);
  Buf[Len] = -2;  // sentinel
  BuildSuffixArray();
  if (false) {
    for (I32 i = 0; i < Len; i++) {
      printf("%" PRIdFAST32 "\t%" PRIdLEAST32 "\t%" PRIdLEAST32 "\t%.*s\n", i,
             SufArr[i], LongCommPre[i], (int)(Len - SufArr[i]),
             Buf + SufArr[i]);
    }
  }
  BuildCumCount2();
  FindCommonStrings();
}
Автор: David Eisenstat Размещён: 18.12.2016 10:49

0 плюса

1430 Репутация автора

Из того, что я могу понять, разбиение строки на все возможные подстроки само по себе является операцией O (n * n).

abcd
====
a,b,c,d
ab,bc,cd
abc,bcd
abcd
************************
abcdefgh
========
a,b,c,d,e,f,g,h
ab,bc,cd,de,ef,fg,gh
abc,bcd,cde,def,efg,fgh
abcd,bcde,cdef,defg,efgh
abcde,bcdef,cdefg,defgh
abcdef,bcdefg,cdefgh
abcdefg,bcdefgh
abcdefgh

Как таковое, оно не выглядит возможным в линейном времени.

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

Затем повторите шаг для второй строки.

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

Если вы используете 'C', то вы можете попробовать отсортировать массив подстрок, а затем использовать двоичный поиск для поиска совпадений (имея двумерный массив для отслеживания строки и количества вхождений).

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

Автор: Ravindra HV Размещён: 21.12.2016 08:34
Вопросы из категории :
32x32