SHARE
TWEET

Untitled

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