Line data    Source code

       1              : // Copyright 2026 The Authors.
       2              : //
       3              : // Licensed under the Apache License, Version 2.0 (the "License");
       4              : // you may not use this file except in compliance with the License.
       5              : // You may obtain a copy of the License at
       6              : //
       7              : //     https://www.apache.org/licenses/LICENSE-2.0
       8              : //
       9              : // Unless required by applicable law or agreed to in writing, software
      10              : // distributed under the License is distributed on an "AS IS" BASIS,
      11              : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12              : // See the License for the specific language governing permissions and
      13              : // limitations under the License.
      14              : 
      15              : /// Matches a maximal run of Unicode letters and combining marks — a "word"
      16              : /// for n-gram extraction purposes. Anything else (whitespace, digits,
      17              : /// punctuation, symbols) acts as a word separator and is discarded.
      18           12 : final RegExp _wordPattern = RegExp(r'\p{L}[\p{L}\p{M}]*', unicode: true);
      19              : 
      20              : /// Word-boundary padding marker, prepended and appended to each word before
      21              : /// n-grams are extracted (e.g. `"the"` -> `"_the_"`).
      22              : const String _boundary = '_';
      23              : 
      24              : /// Smallest and largest n-gram order extracted, inclusive.
      25              : const int _minOrder = 1;
      26              : const int _maxOrder = 5;
      27              : 
      28              : /// Extracts character n-grams (orders 1-5) from [text], ranked by descending
      29              : /// total frequency (summed across all occurrences in [text]), returning at
      30              : /// most [limit] entries. Ties are broken by ascending `String.compareTo`
      31              : /// order (UTF-16 code-unit order) on the n-gram string, for determinism.
      32              : ///
      33              : /// This function is shared verbatim between the codegen tool
      34              : /// (`tool/generate_ngram_profiles.dart`, which builds each language's
      35              : /// reference profile) and the runtime scorer (`NgramBackend`, which extracts
      36              : /// the same kind of ranked list from arbitrary input text). Using the same
      37              : /// function for both is a correctness invariant: if profile generation and
      38              : /// query-time extraction ever tokenized text differently, the two would
      39              : /// silently drift apart with no test able to catch it short of an
      40              : /// end-to-end accuracy benchmark.
      41              : ///
      42              : /// Words are maximal runs of Unicode letters and combining marks, lowercased,
      43              : /// then padded with a single `_` boundary marker on each side (`"the"` ->
      44              : /// `"_the_"`). N-grams are all contiguous substrings of the padded word of
      45              : /// length 1 through 5 (or up to the padded word's length if shorter).
      46              : ///
      47              : /// Example:
      48              : /// ```dart
      49              : /// extractRankedNgrams('the cat sat', limit: 5);
      50              : /// // Padded words: "_the_", "_cat_", "_sat_"
      51              : /// // -> a ranked list of their 1-5 order substrings, most frequent first.
      52              : /// ```
      53            4 : List<String> extractRankedNgrams(String text, {int limit = 300}) {
      54            4 :   final counts = <String, int>{};
      55              : 
      56           12 :   for (final match in _wordPattern.allMatches(text)) {
      57           12 :     final padded = '$_boundary${match.group(0)!.toLowerCase()}$_boundary';
      58           12 :     final maxOrder = _maxOrder < padded.length ? _maxOrder : padded.length;
      59            8 :     for (var order = _minOrder; order <= maxOrder; order++) {
      60           16 :       for (var start = 0; start + order <= padded.length; start++) {
      61            8 :         final ngram = padded.substring(start, start + order);
      62           12 :         counts[ngram] = (counts[ngram] ?? 0) + 1;
      63              :       }
      64              :     }
      65              :   }
      66              : 
      67            8 :   final ranked = counts.keys.toList()
      68            8 :     ..sort((a, b) {
      69           12 :       final byCount = counts[b]!.compareTo(counts[a]!);
      70            8 :       return byCount != 0 ? byCount : a.compareTo(b);
      71              :     });
      72              : 
      73            9 :   return ranked.length > limit ? ranked.sublist(0, limit) : ranked;
      74              : }