Dynamic Pattern Matching (固定本文)

string/dynamic_pattern_matching.hpp · GitHub で見る

共通ページ

固定した本文に対して、パターンを編集しながら出現回数と出現位置を求めます。文字の挿入・削除・置換、部分文字列の削除・移動・コピーに対応します。照合は厳密で、ハッシュの衝突はありません。

#include "lib/string/dynamic_pattern_matching.hpp"

int main() {
	DynamicPatternMatching matching("banana", "ana");
	assert(matching.count() == 2);
	assert((matching.occurrences() == std::vector<int>{3, 1}));
	matching.erase(1);
	assert(matching.str() == "aa" && matching.count() == 0);
	matching.insert(1, 'n');
	assert(matching.count() == 2);
	auto saved = matching;
	matching.copy(0, 3, 3);
	assert(matching.str() == "anaana" && matching.count() == 0);
	assert(saved.str() == "ana" && saved.count() == 2);
	matching.erase(0, 3);
	assert(matching.count() == 2);
	matching.assign("ban");
	matching.move(0, 1, 2);
	assert(matching.str() == "anb");
	matching.clear();
	assert(matching.count() == 7);
	matching.compact();
}

本文とパターンは std::string_view で渡します。バイト単位で扱い、NUL を含む全 256 種類に対応します。入力した文字列はコピーするため、呼び出し後に元の文字列を変更・破棄できます。本文は INT_MAX/2 バイト未満、パターン長と位置は uint64_t の範囲です。パターンを編集しても本文は変わりません。本文の変更には build での再構築が必要です。

添字は全て 0 始まり、区間は [l,r) です。insert(p,...) と copy(l,r,p) の挿入位置は、操作前のパターンの p 文字目の直前です。p == size() なら末尾に挿入します。copy は、操作前の [l,r) をコピーするので、p がコピー元の内部でも使えます。

move(l,r,p) の p は 元の区間を削除した後 の位置です。例えば abcdef に move(1,3,4) を行うと、bc を取り除いた adef の位置 4 に挿入し、adefbc になります。0 <= p <= size()-(r-l) を満たしてください。空区間の削除・移動・コピーは何もしません。コピーや挿入の後の長さが UINT64_MAX を超えないようにしてください。

count() は重なりを含めた出現回数です。空のパターンは本文の位置 0～text().size() に現れるため、出現回数は本文長に 1 を足した値です。本文にない文字を含む場合や、パターンが本文より長い場合の出現回数は 0 です。

occurrences() は出現位置を 接尾辞の辞書順 に返します。位置の昇順が必要な場合は返り値をソートしてください。occurrence(i) はその i 番目を配列を作らず取得します。occurrence_range() の [l,r) は本文上の区間ではなく、suffix_array() 上の区間です。出現位置は suffix_array()[l]～suffix_array()[r-1] です。この接尾辞配列は空の接尾辞も含み、長さは本文長に 1 を足した値、先頭は本文長です。

コピー構築・コピー代入では本文と木を共有します。その後の編集はコピー元に影響しないため、auto saved = matching; として状態を保存できます。ムーブ元は本文・パターンとも空になります。文字列を展開する str() はパターン長に比例する出力を作るため、巨大なコピーの後は count()・operator[] などを使ってください。

部分文字列のコピーは木を共有して処理します。編集で不要になった木の節点はその場で破棄せず、記憶領域に残します。clear()・assign() でも節点の記憶領域は残ります。長期間編集を続ける場合は、適宜 compact() で現在の状態から到達できない節点を取り除いてください。保存した別のコピーがある場合、そのコピーの記憶領域は解放されません。storage_nodes() は共有する記憶領域の節点数を返し、現在のパターンの断片数とは異なります。節点番号は内部で int を使うため、保持節点数は INT_MAX 未満にしてください。

String Matching with a Dynamic Pattern の固定本文版を実装しています。本文に出現する断片と、本文にない 1 バイトの断片でパターンを表し、隣り合う断片を結合しても本文に現れない状態を保ちます。編集時は境界付近だけを直します。断片間の結合は接尾辞配列と逆配列で二分探索し、断片の切り出しは LCP 配列上のセグメント木で探索します。これにより RMQ の追加の対数因子を前処理に持ち込まず、線形時間・空間で本文の索引を作ります。木は共有可能な永続 AVL 木です。論文第7節の本文への文字追加は扱いません。

本文長を \(n\)、操作前後のパターン長の最大を \(m\)、渡す文字列の長さを \(s\)、出現回数を \(k\)、共有して保持する節点数を \(A\) とします。対数の項は長さが 0・1 の場合に定数として扱います。† は節点を格納する配列の伸長を含む償却計算量です。

操作	内容・返り値	計算量
DynamicPatternMatching()	本文・パターンとも空の状態を作る	\(O(1)\)
DynamicPatternMatching(text,pattern={})	本文の索引と初期パターンを作る	\(O(n+s)\)
build(text,pattern={})	本文とパターンを作り直す	新規構築 \(O(n+s)\) と旧記憶領域の解放
assign(pattern)	パターンを渡した文字列に置き換える	† \(O(s)\)
clear()	パターンを空にする	\(O(1)\)
size() / empty()	パターン長 / パターンが空か	\(O(1)\)
text()	固定した本文の string_view	\(O(1)\)
insert(p,c)	位置 p に 1 バイト挿入	† \(O(\log n+\log m)\)
insert(p,pattern)	位置 p に文字列を挿入	† \(O(s+\log n+\log m)\)
erase(p) / erase(l,r)	1 バイト / 区間を削除	† \(O(\log n+\log m)\)
set(p,c)	位置 p を 1 バイトに置換	† \(O(\log n+\log m)\)
move(l,r,p)	区間を削除後の位置 p に移動	† \(O(\log n+\log m)\)
copy(l,r,p)	区間のコピーを操作前の位置 p に挿入	† \(O(\log n+\log m)\)
count()	出現回数を int で返す	\(O(1)\)
occurrence(i)	接尾辞配列の順で i 番目の出現位置	\(O(1)\)
occurrences()	全出現位置の vector<int>	\(O(k)\)
occurrence_range()	出現する接尾辞配列の区間 [l,r)	\(O(1)\)
suffix_array()	空の接尾辞を含む接尾辞配列への const 参照	\(O(1)\)
operator[](p)	パターンの位置 p のバイト	\(O(\log m)\)
str()	現在のパターン全体を string に展開	\(O(m)\)
storage_nodes()	共有する節点記憶領域の保持節点数	\(O(1)\)
compact()	本文の索引は共有し、現在必要な節点だけを新しい記憶領域に移す	\(O(A)\) 時間・追加空間
コピー構築 / コピー代入	本文・木を共有して状態を保存	構築 \(O(1)\)、代入は旧記憶領域の解放が加わる
ムーブ構築 / ムーブ代入	状態を移し、移動元を空に戻す	構築 \(O(1)\)、代入は旧記憶領域の解放が加わる
swap(other)	状態を交換する	\(O(1)\)

本文の索引は \(O(n)\) 空間です。初期パターンには高々 \(O(s)\) 節点を使います。文字の編集・部分文字列の操作 1 回につき追加する節点数は \(O(\log m)\)、長さ \(s\) の文字列の代入・挿入ではさらに \(O(s)\) です。最後に共有状態が破棄される際は、その記憶領域の解放が発生します。パターン長を本文長以下に保つ場合、編集の計算量は論文と同じ † \(O(\log n)\) です。

依存ライブラリ

• Default Init Allocator
• Persistent Rope Core
• 共通接頭辞・接尾辞の比較
• Static Range Min
• Suffix Array Core
• Suffix Range Core
• Sparse Table
• Suffix Tree (静的文字列)

検証コード

• test/dynamic_pattern_matching_array.test.cpp

コード

#ifndef DYNAMIC_PATTERN_MATCHING_HPP
#define DYNAMIC_PATTERN_MATCHING_HPP

#include "../components/persistent_rope.hpp"
#include "../components/suffix_range.hpp"
#include <memory>
#include <string>

class DynamicPatternMatching {
	struct Piece { SuffixRangeIndex::Range range; int start = 0; };
	static std::uint64_t weight(const Piece &piece) { return piece.range.length; }
	using Rope = PersistentRope<Piece, weight>;
	struct State {
		std::shared_ptr<const SuffixRangeIndex> index;
		Rope rope;
		explicit State(std::shared_ptr<const SuffixRangeIndex> index) : index(std::move(index)) {}
	};
	std::shared_ptr<State> state_;
	int root_ = 0;
	Rope &rope() const { return state_->rope; }
	const SuffixRangeIndex &index() const { return *state_->index; }
	Piece character(char c) const {
		auto range = index().character(c);
		return {range, range.left < range.right ? index().suffix_array()[range.left] : -int(static_cast<unsigned char>(c)) - 1};
	}
	Piece subpiece(Piece piece, int l, int r) const {
		return {index().substring(piece.range, l, r), piece.start + l};
	}
	int concat(int a, int b) {
		if (!a || !b) return a ? a : b;
		auto x = rope().back(a), y = rope().front(b);
		auto range = index().concat(x.range, y.range);
		if (range.left == range.right) return rope().join(a, b);
		int left = rope().pop_back(a).first, right = rope().pop_front(b).second;
		int middle = rope().make(Piece{range, index().suffix_array()[range.left]});
		return rope().join(rope().join(left, middle), right);
	}
	std::pair<int, int> split(int root, std::uint64_t p) {
		bool divided = false;
		auto result = rope().split(root, p, [&](Piece piece, std::uint64_t offset) {
			divided = true;
			int k = static_cast<int>(offset);
			return std::pair{subpiece(piece, 0, k), subpiece(piece, k, piece.range.length)};
		});
		if (!divided) return result;
		auto &[a, b] = result;
		if (a && !rope().leaf(a)) {
			auto [rest, last] = rope().pop_back(a);
			a = concat(rest, rope().make(last));
		}
		if (b && !rope().leaf(b)) {
			auto [first, rest] = rope().pop_front(b);
			b = concat(rope().make(first), rest);
		}
		return result;
	}
	int make(std::string_view pattern) {
		std::vector<Piece> pieces;
		while (!pattern.empty()) {
			auto [range, length] = index().longest_prefix(pattern);
			if (!length) { pieces.push_back(character(pattern.front())); length = 1; }
			else pieces.push_back({range, index().suffix_array()[range.left]});
			pattern.remove_prefix(length);
		}
		return rope().build(pieces);
	}
	void check_range([[maybe_unused]] std::uint64_t l, [[maybe_unused]] std::uint64_t r) const { assert(l <= r && r <= size()); }
	void check_growth([[maybe_unused]] std::uint64_t length) const { assert(length <= std::numeric_limits<std::uint64_t>::max() - size()); }

  public:
	using size_type = std::uint64_t;
	DynamicPatternMatching() : DynamicPatternMatching(std::string_view{}) {}
	explicit DynamicPatternMatching(std::string_view text, std::string_view pattern = {})
		: state_(std::make_shared<State>(std::make_shared<const SuffixRangeIndex>(text))) { root_ = make(pattern); }
	DynamicPatternMatching(const DynamicPatternMatching &) = default;
	DynamicPatternMatching &operator=(const DynamicPatternMatching &) = default;
	DynamicPatternMatching(DynamicPatternMatching &&other) : DynamicPatternMatching() { swap(other); }
	DynamicPatternMatching &operator=(DynamicPatternMatching &&other) {
		if (this != &other) { DynamicPatternMatching next(std::move(other)); swap(next); }
		return *this;
	}
	void build(std::string_view text, std::string_view pattern = {}) { DynamicPatternMatching next(text, pattern); swap(next); }
	void swap(DynamicPatternMatching &other) noexcept { state_.swap(other.state_); std::swap(root_, other.root_); }
	void assign(std::string_view pattern) { root_ = make(pattern); }
	void clear() { root_ = 0; }
	size_type size() const { return rope().size(root_); }
	bool empty() const { return root_ == 0; }
	std::string_view text() const { return index().text(); }
	std::size_t storage_nodes() const { return rope().storage_nodes(); }
	void compact() {
		auto next = std::make_shared<State>(state_->index);
		int root = next->rope.copy_from(rope(), root_);
		state_ = std::move(next); root_ = root;
	}
	void insert(size_type p, char c) {
		assert(p <= size()); check_growth(1);
		auto [a, b] = split(root_, p);
		int middle = rope().make(character(c));
		root_ = concat(concat(a, middle), b);
	}
	void insert(size_type p, std::string_view pattern) {
		assert(p <= size()); check_growth(pattern.size());
		if (pattern.empty()) return;
		int middle = make(pattern);
		auto [a, b] = split(root_, p);
		root_ = concat(concat(a, middle), b);
	}
	void erase(size_type p) { assert(p < size()); erase(p, p + 1); }
	void erase(size_type l, size_type r) {
		check_range(l, r);
		if (l == r) return;
		auto [a, rest] = split(root_, l);
		int b = split(rest, r - l).second;
		root_ = concat(a, b);
	}
	void set(size_type p, char c) { assert(p < size()); erase(p); insert(p, c); }
	void move(size_type l, size_type r, size_type p) {
		check_range(l, r); assert(p <= size() - (r - l));
		if (l == r || p == l) return;
		auto [a, rest] = split(root_, l);
		auto [middle, b] = split(rest, r - l);
		int remaining = concat(a, b);
		auto [left, right] = split(remaining, p);
		root_ = concat(concat(left, middle), right);
	}
	void copy(size_type l, size_type r, size_type p) {
		check_range(l, r); assert(p <= size()); check_growth(r - l);
		if (l == r) return;
		int rest = split(root_, l).second, middle = split(rest, r - l).first;
		auto [a, b] = split(root_, p);
		root_ = concat(concat(a, middle), b);
	}
	std::pair<int, int> occurrence_range() const {
		if (!root_) return {0, index().size() + 1};
		if (!rope().leaf(root_)) return {0, 0};
		auto range = rope().value(root_).range;
		return {range.left, range.right};
	}
	int count() const { auto [l, r] = occurrence_range(); return r - l; }
	int occurrence(int i) const { auto [l, r] = occurrence_range(); assert(0 <= i && i < r - l); return index().suffix_array()[l + i]; }
	std::vector<int> occurrences() const { auto [l, r] = occurrence_range(); return {index().suffix_array().begin() + l, index().suffix_array().begin() + r}; }
	const std::vector<int> &suffix_array() const { return index().suffix_array(); }
	char operator[](size_type p) const {
		auto [piece, offset] = rope().at(root_, p);
		return piece.start < 0 ? static_cast<char>(-piece.start - 1) : text()[piece.start + offset];
	}
	std::string str() const {
		std::string result;
		assert(size() <= result.max_size());
		result.reserve(static_cast<std::size_t>(size()));
		rope().for_each(root_, [&](Piece piece) {
			if (piece.start < 0) result.push_back(static_cast<char>(-piece.start - 1));
			else result.append(text().substr(piece.start, piece.range.length));
		});
		return result;
	}
};

#endif

Back to top page