Нахождение N наиболее часто встречающихся подстрок длины K в большом наборе строк - PullRequest
Новая
       26

Нахождение N наиболее часто встречающихся подстрок длины K в большом наборе строк

0 голосов
/ 06 июля 2019

Как видно из названия, я пытаюсь найти N наиболее часто встречающихся подстрок длины K и их частоту в большом количестве строк. Строки читаются из файла построчно. (примерно 5 миллионов строк). Например, если входной файл -

TTTTTGCAG

GCAGGTTTT

и K = 4, N = 2, тогда результат должен быть,

TTTT - 3 вхождения

GCAG - 2 вхождения

Файл образца состоит из последовательностей ДНК. Однако я хочу заключить обобщенное решение.

То, что я сделал до сих пор:

  1. Читать все строки в std::vector<std::string>
  2. Инициализация хэш-карты std::unoredered_map<std::string_view, unsigned int>
  3. Для каждой строки получить все line.length()-K+1 подстроки.
  4. Для каждой подстроки, если она уже есть в нашем приращении карты, это частота, в противном случае вставьте его.
  5. Перенести все записи нашей карты в std::multimap<unsigned int, std::string_view>, получить последние N значений и распечатать их.

Я использовал string_view вместо strings, чтобы получить подстроки более эффективно и не тратить память на каждый ключ.

Этот подход работает, но я пытаюсь найти более оптимальное решение. Я думаю, что проблема заключается в том, что по мере увеличения размера ввода среднее время вставки / поиска в hashmap становится O(N) вместо O(1). Это правда, и что я могу сделать, чтобы улучшить свое время выполнения / использование памяти?

(я также пробовал пробные версии, но они неэффективны для памяти, даже если размер алфавита равен 4 (A, C, G, T), и обход их, чтобы найти N наиболее часто встречающихся, является другой трудностью)

1 Ответ

0 голосов
/ 06 июля 2019

Один из возможных подходов:

Вместо unordered_map используйте std::vector<std::pair<std::string, int>>, который будет отсортирован по строке. При сканировании всех подстрок каждой строки, которую вы читаете, ищите их с помощью двоичного поиска (std::lower_bound() полезно), вставляя или обновляя соответствующим образом (если это небольшой фиксированный алфавит, такой как ДНК, вы можете даже сгенерировать всю длину - K подстроки опережают время и предварительно заполняют вектор, чтобы избежать вставки позже).

Когда закончите, пересортируйте вектор на основе отсчетов в порядке убывания ... std::partial_sort() было бы действительно удобно, так как вам нужны только первые N элементы: 

std::partial_sort(words.begin(), words.begin() + N, words.end(),
                  [](const auto &a, const auto &b){ return a.second > b.second; });

По сути, что-то вроде: 

#include <string>
#include <string_view>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdlib>

constexpr std::size_t K = 4;
constexpr std::size_t N = 2;

int main() {
  std::vector<std::pair<std::string, int>> words;
  std::string line;

  while (std::getline(std::cin, line)) {
    auto len = line.size();
    for (auto i = 0U; i < len - K + 1; i += 1) {
      auto word = std::string_view(line.c_str() + i, K);
      auto pos = std::lower_bound(words.begin(), words.end(), word,
                                  [](const auto &a, const auto &b){
                                    return a.first < b;
                                  });
      if (pos == words.end() || pos->first != word) {
        words.emplace(pos, std::string(word), 1);
      } else {
        pos->second += 1;
      }
    }
  }

  auto sort_to = std::min(words.size(), N);
  std::partial_sort(words.begin(), words.begin() + sort_to, words.end(),
                    [](const auto &a, const auto &b){
                      return a.second > b.second;
                    });
  for (auto i = 0U; i < sort_to; i += 1) {
    std::cout << words[i].first << " - " << words[i].second << " occurences\n";
  }

  return 0;
}
...