SHARE
TWEET

Untitled

a guest Oct 23rd, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python3
  2.  
  3. """
  4. Реализация алгоритма поиска подстрок Aхо-Корасик.
  5. Пример использования:
  6.  
  7. patterns = ['a', 'ab', 'abc', 'bc', 'c', 'cba']
  8. target_string = "abcba"
  9. searcher = AhoCorasickSearcher(patterns)
  10. searcher.find_all(
  11.    target_string,
  12.    lambda pos, patterns: print(f"At pos {pos} found pattern: {patterns}")
  13. )
  14. """
  15.  
  16. from typing import List, Callable
  17.  
  18.  
  19. class BorNode:
  20.     """Узел префиксного дерева."""
  21.     def __init__(self):
  22.         # Узлы-потомки текущего узла (ключ - символ какой-либо строки-паттерна,
  23.         # значение - объект BorNode).
  24.         self.children = {}
  25.         # Совпавшие паттерны.
  26.         self.matched_patterns = []
  27.         # Суффиксная ссылка (ссылка на BorNode, соответствующий самому длинному
  28.         # суффиксу).
  29.         self.suffix_link = None
  30.  
  31.  
  32. class AhoCorasickSearcher:
  33.     """Реализует алгоритм поиска подстрок Ахо-Корасик."""
  34.     def __init__(self, patterns: List[str]):
  35.         """
  36.        Args:
  37.            patterns: паттерны (подстроки), которые нужно будет искать в строке.
  38.        """
  39.         self._root_node = self._create_state_machine(patterns)
  40.  
  41.     @staticmethod
  42.     def _build_prefix_tree(patterns: List[str]):
  43.         """Создает бор - префиксное дерево из паттернов поиска."""
  44.         root = BorNode()
  45.  
  46.         for path in patterns:
  47.             node = root
  48.             for symbol in path:
  49.                 if symbol not in node.children:
  50.                     node.children[symbol] = BorNode()
  51.                     node = node.children[symbol]
  52.             # Для каждого листка дерева, в который прийдет автомат, он будет
  53.             # в конечном состоянии, что будет означать, что данный паттерн path
  54.             # присутствует в строке, по который происходил поиск.
  55.             # Поэтому нужно добавить в этот список паттернов листка паттерн path.
  56.             node.matched_patterns.append(path)
  57.         return root
  58.  
  59.     def _create_state_machine(self, patterns: List[str]):
  60.         """
  61.        Создает конечный автомат: для всех узлов дерева находит и присваивает
  62.        суффиксные ссылки.
  63.        """
  64.         # Создаем бор, инициализируем непосредственных потомков корневого узла.
  65.         root = self._build_prefix_tree(patterns)
  66.         queue = []
  67.         for node in root.children.values():
  68.             queue.append(node)
  69.             node.fail = root
  70.  
  71.         # Идет поиск вширь по префиксному дереву.
  72.         while len(queue) > 0:
  73.             node = queue.pop(0)
  74.  
  75.             for symbol, child_node in node.children.items():
  76.                 # Добавляем очередной узел-потомок в очередь для корректного
  77.                 # дальнейшего поиска вширь по дереву.
  78.                 queue.append(child_node)
  79.                 # Сначала начинает с суфиксной ссылки текущего узла node.
  80.                 # Эта ссылка ведет на узел, описывающий состояние автомата, в
  81.                 # которое он перейдет, если прекратиться matching в строке.
  82.                 fail_node = node.suffix_link
  83.                 # Поиск самой длинной суффиксной ссылки для узла-потомка.
  84.                 while fail_node is not None and symbol not in fail_node.children:
  85.                     fail_node = fail_node.suffix_link
  86.                 if fail_node is not None:
  87.                     child_node.suffix_link = child_node.children[symbol]
  88.                 else:
  89.                     child_node.suffix_link = root
  90.  
  91.                 # Добавляем в текущий узел-потомок паттерны из узла по
  92.                 # суффиксной ссылке. Это нужно, чтобы не пропустить паттерны
  93.                 # которые бы мы получили если бы пошли по ветке дерева, которая
  94.                 # привела бы нас в child_node.suffix_link сразу.
  95.                 child_node.matched_patterns.extend(
  96.                     child_node.suffix_link.matched_patterns
  97.                 )
  98.         # Возвращаем ссылку на дерево-автомат.
  99.         return root
  100.  
  101.     def find_all(self, target_string, matching_handler: Callable[[int, List[str]], None]):
  102.         """
  103.        Находит все возможные подстроки из набора паттернов в строке.
  104.  
  105.        Args:
  106.            target_string: строка, по которой происходит поиск паттернов.
  107.            matching_handler: обработчик совпадения какой-либо части строки
  108.                target_string с некоторыми паттернами.
  109.        """
  110.         node = self._root_node
  111.  
  112.         for i, symbol in enumerate(target_string):
  113.             # Если в какой-то момент при matching'е мы пришли в "неудачный" узел,
  114.             # т.е. в узел, на котором matching прекратился, то нужно перевести
  115.             # автомат в нужное состояние - перейти по суффиксной ссылке.
  116.             while node is not None and symbol not in node.children:
  117.                 node = node.fail
  118.             # Если очередная итерация matching'а закончилась в корневом узле,
  119.             # то назначаем его текущему узлу для последующих итераций.
  120.             if node is None:
  121.                 node = self._root_node
  122.                 continue
  123.             # Если выполнение дошло до этого места, symbol ведет из текущего
  124.             # узла node в другой, т.е. итерация матчинга завершилась "успешно".
  125.             # Тогда запоминаем следующий узел, как текущий. И вызываем функцию-
  126.             # обработчик со всеми паттернами, которые сохранены в нем (если,
  127.             # конечно, этот узел терминальный и там паттерны вообще есть).
  128.             node = node.children[symbol]
  129.             for pattern in node.matched_patterns:
  130.                 matching_handler(i - len(pattern) + 1, pattern)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top