suffix_array.h 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476
  1. // Copyright 2017 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef COMPONENTS_ZUCCHINI_SUFFIX_ARRAY_H_
  5. #define COMPONENTS_ZUCCHINI_SUFFIX_ARRAY_H_
  6. #include <algorithm>
  7. #include <iterator>
  8. #include <numeric>
  9. #include <vector>
  10. #include "base/check.h"
  11. #include "base/containers/adapters.h"
  12. namespace zucchini {
  13. // A functor class that implements the naive suffix sorting algorithm that uses
  14. // std::sort with lexicographical compare. This is only meant as reference of
  15. // the interface.
  16. class NaiveSuffixSort {
  17. public:
  18. // Type requirements:
  19. // |InputRng| is an input random access range.
  20. // |KeyType| is an unsigned integer type.
  21. // |SAIt| is a random access iterator with mutable references.
  22. template <class InputRng, class KeyType, class SAIt>
  23. // |str| is the input string on which suffix sort is applied.
  24. // Characters found in |str| must be in the range [0, |key_bound|)
  25. // |suffix_array| is the beginning of the destination range, which is at least
  26. // as large as |str|.
  27. void operator()(const InputRng& str,
  28. KeyType key_bound,
  29. SAIt suffix_array) const {
  30. using size_type = typename SAIt::value_type;
  31. size_type n = static_cast<size_type>(std::end(str) - std::begin(str));
  32. // |suffix_array| is first filled with ordered indices of |str|.
  33. // Those indices are then sorted with lexicographical comparisons in |str|.
  34. std::iota(suffix_array, suffix_array + n, 0);
  35. std::sort(suffix_array, suffix_array + n, [&str](size_type i, size_type j) {
  36. return std::lexicographical_compare(std::begin(str) + i, std::end(str),
  37. std::begin(str) + j, std::end(str));
  38. });
  39. }
  40. };
  41. // A functor class that implements suffix array induced sorting (SA-IS)
  42. // algorithm with linear time and memory complexity,
  43. // see http://ieeexplore.ieee.org/abstract/document/5582081/
  44. class InducedSuffixSort {
  45. public:
  46. // Type requirements:
  47. // |InputRng| is an input random access range.
  48. // |KeyType| is an unsigned integer type.
  49. // |SAIt| is a random access iterator with mutable values.
  50. template <class InputRng, class KeyType, class SAIt>
  51. // |str| is the input string on which suffix sort is applied.
  52. // Characters found in |str| must be in the range [0, |key_bound|)
  53. // |suffix_array| is the beginning of the destination range, which is at least
  54. // as large as |str|.
  55. void operator()(const InputRng& str,
  56. KeyType key_bound,
  57. SAIt suffix_array) const {
  58. using value_type = typename InputRng::value_type;
  59. using size_type = typename SAIt::value_type;
  60. static_assert(std::is_unsigned<value_type>::value,
  61. "SA-IS only supports input string with unsigned values");
  62. static_assert(std::is_unsigned<KeyType>::value, "KeyType must be unsigned");
  63. size_type n = static_cast<size_type>(std::end(str) - std::begin(str));
  64. Implementation<size_type, KeyType>::SuffixSort(std::begin(str), n,
  65. key_bound, suffix_array);
  66. }
  67. // Given string S of length n. We assume S is terminated by a unique sentinel
  68. // $, which is considered as the smallest character. This sentinel does not
  69. // exist in memory and is only treated implicitly, hence |n| does not count
  70. // the sentinel in this implementation. We denote suf(S,i) the suffix formed
  71. // by S[i..n).
  72. // A suffix suf(S,i) is said to be S-type or L-type, if suf(S,i) < suf(S,i+1)
  73. // or suf(S,i) > suf(S,i+1), respectively.
  74. enum SLType : bool { SType, LType };
  75. // A character S[i] is said to be S-type or L-type if the suffix suf(S,i) is
  76. // S-type or L-type, respectively.
  77. // A character S[i] is called LMS (leftmost S-type), if S[i] is S-type and
  78. // S[i-1] is L-type. A suffix suf(S,i) is called LMS, if S[i] is an LMS
  79. // character.
  80. // A substring S[i..j) is an LMS-substring if
  81. // (1) S[i] is LMS, S[j] is LMS or the sentinel $, and S[i..j) has no other
  82. // LMS characters, or
  83. // (2) S[i..j) is the sentinel $.
  84. template <class SizeType, class KeyType>
  85. struct Implementation {
  86. static_assert(std::is_unsigned<SizeType>::value,
  87. "SizeType must be unsigned");
  88. static_assert(std::is_unsigned<KeyType>::value, "KeyType must be unsigned");
  89. using size_type = SizeType;
  90. using key_type = KeyType;
  91. using iterator = typename std::vector<size_type>::iterator;
  92. using const_iterator = typename std::vector<size_type>::const_iterator;
  93. // Partition every suffix based on SL-type. Returns the number of LMS
  94. // suffixes.
  95. template <class StrIt>
  96. static size_type BuildSLPartition(
  97. StrIt str,
  98. size_type length,
  99. key_type key_bound,
  100. std::vector<SLType>::reverse_iterator sl_partition_it) {
  101. // We will count LMS suffixes (S to L-type or last S-type).
  102. size_type lms_count = 0;
  103. // |previous_type| is initialized to L-type to avoid counting an extra
  104. // LMS suffix at the end
  105. SLType previous_type = LType;
  106. // Initialized to dummy, impossible key.
  107. key_type previous_key = key_bound;
  108. // We're travelling backward to determine the partition,
  109. // as if we prepend one character at a time to the string, ex:
  110. // b$ is L-type because b > $.
  111. // ab$ is S-type because a < b, implying ab$ < b$.
  112. // bab$ is L-type because b > a, implying bab$ > ab$.
  113. // bbab$ is L-type, because bab$ was also L-type, implying bbab$ > bab$.
  114. for (auto str_it = std::reverse_iterator<StrIt>(str + length);
  115. str_it != std::reverse_iterator<StrIt>(str);
  116. ++str_it, ++sl_partition_it) {
  117. key_type current_key = *str_it;
  118. if (current_key > previous_key || previous_key == key_bound) {
  119. // S[i] > S[i + 1] or S[i] is last character.
  120. if (previous_type == SType)
  121. // suf(S,i) is L-type and suf(S,i + 1) is S-type, therefore,
  122. // suf(S,i+1) was a LMS suffix.
  123. ++lms_count;
  124. previous_type = LType; // For next round.
  125. } else if (current_key < previous_key) {
  126. // S[i] < S[i + 1]
  127. previous_type = SType; // For next round.
  128. }
  129. // Else, S[i] == S[i + 1]:
  130. // The next character that differs determines the SL-type,
  131. // so we reuse the last seen type.
  132. *sl_partition_it = previous_type;
  133. previous_key = current_key; // For next round.
  134. }
  135. return lms_count;
  136. }
  137. // Find indices of LMS suffixes and write result to |lms_indices|.
  138. static void FindLmsSuffixes(const std::vector<SLType>& sl_partition,
  139. iterator lms_indices) {
  140. // |previous_type| is initialized to S-type to avoid counting an extra
  141. // LMS suffix at the beginning
  142. SLType previous_type = SType;
  143. for (size_type i = 0; i < sl_partition.size(); ++i) {
  144. if (sl_partition[i] == SType && previous_type == LType)
  145. *lms_indices++ = i;
  146. previous_type = sl_partition[i];
  147. }
  148. }
  149. template <class StrIt>
  150. static std::vector<size_type> MakeBucketCount(StrIt str,
  151. size_type length,
  152. key_type key_bound) {
  153. // Occurrence of every unique character is counted in |buckets|
  154. std::vector<size_type> buckets(static_cast<size_type>(key_bound));
  155. for (auto it = str; it != str + length; ++it)
  156. ++buckets[*it];
  157. return buckets;
  158. }
  159. // Apply induced sort from |lms_indices| to |suffix_array| associated with
  160. // the string |str|.
  161. template <class StrIt, class SAIt>
  162. static void InducedSort(StrIt str,
  163. size_type length,
  164. const std::vector<SLType>& sl_partition,
  165. const std::vector<size_type>& lms_indices,
  166. const std::vector<size_type>& buckets,
  167. SAIt suffix_array) {
  168. // All indices are first marked as unset with the illegal value |length|.
  169. std::fill(suffix_array, suffix_array + length, length);
  170. // Used to mark bucket boundaries (head or end) as indices in str.
  171. DCHECK(!buckets.empty());
  172. std::vector<size_type> bucket_bounds(buckets.size());
  173. // Step 1: Assign indices for LMS suffixes, populating the end of
  174. // respective buckets but keeping relative order.
  175. // Find the end of each bucket and write it to |bucket_bounds|.
  176. std::partial_sum(buckets.begin(), buckets.end(), bucket_bounds.begin());
  177. // Process each |lms_indices| backward, and assign them to the end of
  178. // their respective buckets, so relative order is preserved.
  179. for (size_t lms_index : base::Reversed(lms_indices)) {
  180. key_type key = str[lms_index];
  181. suffix_array[--bucket_bounds[key]] = lms_index;
  182. }
  183. // Step 2
  184. // Scan forward |suffix_array|; for each modified suf(S,i) for which
  185. // suf(S,SA(i) - 1) is L-type, place suf(S,SA(i) - 1) to the current
  186. // head of the corresponding bucket and forward the bucket head to the
  187. // right.
  188. // Find the head of each bucket and write it to |bucket_bounds|. Since
  189. // only LMS suffixes where inserted in |suffix_array| during Step 1,
  190. // |bucket_bounds| does not contains the head of each bucket and needs to
  191. // be updated.
  192. bucket_bounds[0] = 0;
  193. std::partial_sum(buckets.begin(), buckets.end() - 1,
  194. bucket_bounds.begin() + 1);
  195. // From Step 1, the sentinel $, which we treat implicitly, would have
  196. // been placed at the beginning of |suffix_array|, since $ is always
  197. // considered as the smallest character. We then have to deal with the
  198. // previous (last) suffix.
  199. if (sl_partition[length - 1] == LType) {
  200. key_type key = str[length - 1];
  201. suffix_array[bucket_bounds[key]++] = length - 1;
  202. }
  203. for (auto it = suffix_array; it != suffix_array + length; ++it) {
  204. size_type suffix_index = *it;
  205. // While the original algorithm marks unset suffixes with -1,
  206. // we found that marking them with |length| is also possible and more
  207. // convenient because we are working with unsigned integers.
  208. if (suffix_index != length && suffix_index > 0 &&
  209. sl_partition[--suffix_index] == LType) {
  210. key_type key = str[suffix_index];
  211. suffix_array[bucket_bounds[key]++] = suffix_index;
  212. }
  213. }
  214. // Step 3
  215. // Scan backward |suffix_array|; for each modified suf(S, i) for which
  216. // suf(S,SA(i) - 1) is S-type, place suf(S,SA(i) - 1) to the current
  217. // end of the corresponding bucket and forward the bucket head to the
  218. // left.
  219. // Find the end of each bucket and write it to |bucket_bounds|. Since
  220. // only L-type suffixes where inserted in |suffix_array| during Step 2,
  221. // |bucket_bounds| does not contain the end of each bucket and needs to
  222. // be updated.
  223. std::partial_sum(buckets.begin(), buckets.end(), bucket_bounds.begin());
  224. for (auto it = std::reverse_iterator<SAIt>(suffix_array + length);
  225. it != std::reverse_iterator<SAIt>(suffix_array); ++it) {
  226. size_type suffix_index = *it;
  227. if (suffix_index != length && suffix_index > 0 &&
  228. sl_partition[--suffix_index] == SType) {
  229. key_type key = str[suffix_index];
  230. suffix_array[--bucket_bounds[key]] = suffix_index;
  231. }
  232. }
  233. // Deals with the last suffix, because of the sentinel.
  234. if (sl_partition[length - 1] == SType) {
  235. key_type key = str[length - 1];
  236. suffix_array[--bucket_bounds[key]] = length - 1;
  237. }
  238. }
  239. // Given a string S starting at |str| with length |length|, an array
  240. // starting at |substring_array| containing lexicographically ordered LMS
  241. // terminated substring indices of S and an SL-Type partition |sl_partition|
  242. // of S, assigns a unique label to every unique LMS substring. The sorted
  243. // labels for all LMS substrings are written to |lms_str|, while the indices
  244. // of LMS suffixes are written to |lms_indices|. In addition, returns the
  245. // total number of unique labels.
  246. template <class StrIt, class SAIt>
  247. static size_type LabelLmsSubstrings(StrIt str,
  248. size_type length,
  249. const std::vector<SLType>& sl_partition,
  250. SAIt suffix_array,
  251. iterator lms_indices,
  252. iterator lms_str) {
  253. // Labelling starts at 0.
  254. size_type label = 0;
  255. // |previous_lms| is initialized to 0 to indicate it is unset.
  256. // Note that suf(S,0) is never a LMS suffix. Substrings will be visited in
  257. // lexicographical order.
  258. size_type previous_lms = 0;
  259. for (auto it = suffix_array; it != suffix_array + length; ++it) {
  260. if (*it > 0 && sl_partition[*it] == SType &&
  261. sl_partition[*it - 1] == LType) {
  262. // suf(S, *it) is a LMS suffix.
  263. size_type current_lms = *it;
  264. if (previous_lms != 0) {
  265. // There was a previous LMS suffix. Check if the current LMS
  266. // substring is equal to the previous one.
  267. SLType current_lms_type = SType;
  268. SLType previous_lms_type = SType;
  269. for (size_type k = 0;; ++k) {
  270. // |current_lms_end| and |previous_lms_end| denote whether we have
  271. // reached the end of the current and previous LMS substring,
  272. // respectively
  273. bool current_lms_end = false;
  274. bool previous_lms_end = false;
  275. // Check for both previous and current substring ends.
  276. // Note that it is more convenient to check if
  277. // suf(S,current_lms + k) is an LMS suffix than to retrieve it
  278. // from lms_indices.
  279. if (current_lms + k >= length ||
  280. (current_lms_type == LType &&
  281. sl_partition[current_lms + k] == SType)) {
  282. current_lms_end = true;
  283. }
  284. if (previous_lms + k >= length ||
  285. (previous_lms_type == LType &&
  286. sl_partition[previous_lms + k] == SType)) {
  287. previous_lms_end = true;
  288. }
  289. if (current_lms_end && previous_lms_end) {
  290. break; // Previous and current substrings are identical.
  291. } else if (current_lms_end != previous_lms_end ||
  292. str[current_lms + k] != str[previous_lms + k]) {
  293. // Previous and current substrings differ, a new label is used.
  294. ++label;
  295. break;
  296. }
  297. current_lms_type = sl_partition[current_lms + k];
  298. previous_lms_type = sl_partition[previous_lms + k];
  299. }
  300. }
  301. *lms_indices++ = *it;
  302. *lms_str++ = label;
  303. previous_lms = current_lms;
  304. }
  305. }
  306. return label + 1;
  307. }
  308. // Implementation of the SA-IS algorithm. |str| must be a random access
  309. // iterator pointing at the beginning of S with length |length|. The result
  310. // is writtend in |suffix_array|, a random access iterator.
  311. template <class StrIt, class SAIt>
  312. static void SuffixSort(StrIt str,
  313. size_type length,
  314. key_type key_bound,
  315. SAIt suffix_array) {
  316. if (length == 1)
  317. *suffix_array = 0;
  318. if (length < 2)
  319. return;
  320. std::vector<SLType> sl_partition(length);
  321. size_type lms_count =
  322. BuildSLPartition(str, length, key_bound, sl_partition.rbegin());
  323. std::vector<size_type> lms_indices(lms_count);
  324. FindLmsSuffixes(sl_partition, lms_indices.begin());
  325. std::vector<size_type> buckets = MakeBucketCount(str, length, key_bound);
  326. if (lms_indices.size() > 1) {
  327. // Given |lms_indices| in the same order they appear in |str|, induce
  328. // LMS substrings relative order and write result to |suffix_array|.
  329. InducedSort(str, length, sl_partition, lms_indices, buckets,
  330. suffix_array);
  331. std::vector<size_type> lms_str(lms_indices.size());
  332. // Given LMS substrings in relative order found in |suffix_array|,
  333. // map LMS substrings to unique labels to form a new string, |lms_str|.
  334. size_type label_count =
  335. LabelLmsSubstrings(str, length, sl_partition, suffix_array,
  336. lms_indices.begin(), lms_str.begin());
  337. if (label_count < lms_str.size()) {
  338. // Reorder |lms_str| to have LMS suffixes in the same order they
  339. // appear in |str|.
  340. for (size_type i = 0; i < lms_indices.size(); ++i)
  341. suffix_array[lms_indices[i]] = lms_str[i];
  342. SLType previous_type = SType;
  343. for (size_type i = 0, j = 0; i < sl_partition.size(); ++i) {
  344. if (sl_partition[i] == SType && previous_type == LType) {
  345. lms_str[j] = suffix_array[i];
  346. lms_indices[j++] = i;
  347. }
  348. previous_type = sl_partition[i];
  349. }
  350. // Recursively apply SuffixSort on |lms_str|, which is formed from
  351. // labeled LMS suffixes in the same order they appear in |str|.
  352. // Note that |KeyType| will be size_type because |lms_str| contains
  353. // indices. |lms_str| is at most half the length of |str|.
  354. Implementation<size_type, size_type>::SuffixSort(
  355. lms_str.begin(), static_cast<size_type>(lms_str.size()),
  356. label_count, suffix_array);
  357. // Map LMS labels back to indices in |str| and write result to
  358. // |lms_indices|. We're using |suffix_array| as a temporary buffer.
  359. for (size_type i = 0; i < lms_indices.size(); ++i)
  360. suffix_array[i] = lms_indices[suffix_array[i]];
  361. std::copy_n(suffix_array, lms_indices.size(), lms_indices.begin());
  362. // At this point, |lms_indices| contains sorted LMS suffixes of |str|.
  363. }
  364. }
  365. // Given |lms_indices| where LMS suffixes are sorted, induce the full
  366. // order of suffixes in |str|.
  367. InducedSort(str, length, sl_partition, lms_indices, buckets,
  368. suffix_array);
  369. }
  370. Implementation() = delete;
  371. Implementation(const Implementation&) = delete;
  372. const Implementation& operator=(const Implementation&) = delete;
  373. };
  374. };
  375. // Generates a sorted suffix array for the input string |str| using the functor
  376. // |Algorithm| which provides an interface equivalent to NaiveSuffixSort.
  377. /// Characters found in |str| are assumed to be in range [0, |key_bound|).
  378. // Returns the suffix array as a vector.
  379. // |StrRng| is an input random access range.
  380. // |KeyType| is an unsigned integer type.
  381. template <class Algorithm, class StrRng, class KeyType>
  382. std::vector<typename StrRng::size_type> MakeSuffixArray(const StrRng& str,
  383. KeyType key_bound) {
  384. Algorithm sort;
  385. std::vector<typename StrRng::size_type> suffix_array(str.end() - str.begin());
  386. sort(str, key_bound, suffix_array.begin());
  387. return suffix_array;
  388. }
  389. // Type requirements:
  390. // |SARng| is an input random access range.
  391. // |StrIt1| is a random access iterator.
  392. // |StrIt2| is a forward iterator.
  393. template <class SARng, class StrIt1, class StrIt2>
  394. // Lexicographical lower bound using binary search for
  395. // [|str2_first|, |str2_last|) in the suffix array |suffix_array| of a string
  396. // starting at |str1_first|. This does not necessarily return the index of
  397. // the longest matching substring.
  398. auto SuffixLowerBound(const SARng& suffix_array,
  399. StrIt1 str1_first,
  400. StrIt2 str2_first,
  401. StrIt2 str2_last) -> decltype(std::begin(suffix_array)) {
  402. using size_type = typename SARng::value_type;
  403. size_t n = std::end(suffix_array) - std::begin(suffix_array);
  404. auto it = std::lower_bound(
  405. std::begin(suffix_array), std::end(suffix_array), str2_first,
  406. [str1_first, str2_last, n](size_type a, StrIt2 b) {
  407. return std::lexicographical_compare(str1_first + a, str1_first + n, b,
  408. str2_last);
  409. });
  410. return it;
  411. }
  412. } // namespace zucchini
  413. #endif // COMPONENTS_ZUCCHINI_SUFFIX_ARRAY_H_