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              : import '../backend.dart';
      16              : import '../guess.dart';
      17              : import 'ngram_extractor.dart';
      18              : import 'profiles.g.dart';
      19              : 
      20              : /// The profile size used both when generating reference profiles
      21              : /// (`tool/generate_ngram_profiles.dart`) and when extracting a query's own
      22              : /// ranked n-gram list. Also doubles as the maximum "out-of-place" penalty
      23              : /// for an n-gram absent from a profile — the standard choice in the
      24              : /// Cavnar & Trenkle algorithm family (see [NgramBackend]).
      25              : const int ngramProfileSize = 300;
      26              : 
      27              : /// A [LanguageDetectorBackend] implementing Cavnar & Trenkle's
      28              : /// "N-Gram-Based Text Categorization" (1994): each language has a reference
      29              : /// profile — its top-[ngramProfileSize] character n-grams, ranked by
      30              : /// frequency in a training corpus (see `profiles.g.dart`). An input text is
      31              : /// scored against every candidate language's profile by summing, for each of
      32              : /// the input's own top-ranked n-grams, the absolute difference in rank
      33              : /// between the two lists (an "out-of-place" distance); n-grams the profile
      34              : /// doesn't have at all are penalized by the maximum possible amount,
      35              : /// [ngramProfileSize].
      36              : ///
      37              : /// Confidence is **not** a calibrated probability — it is a linear rescaling
      38              : /// of each candidate's distance across the *candidate set being compared*:
      39              : /// the best-scoring candidate gets `1.0`, the worst gets `0.0`, and everyone
      40              : /// else is scaled linearly in between. This means the same input text can
      41              : /// report a different confidence for the same language depending on which
      42              : /// other languages it was compared against (see `restrictTo` on
      43              : /// `LanguageDetector` / `CompositeBackend`) — narrowing the candidate set
      44              : /// sharpens confidence, by design.
      45              : final class NgramBackend implements LanguageDetectorBackend {
      46              :   /// Reference profiles to score against, keyed by language code. Defaults
      47              :   /// to the full generated set (`profiles.g.dart`); a smaller map can be
      48              :   /// passed directly for testing or for a pre-narrowed candidate set.
      49              :   final Map<String, List<String>> _profiles;
      50              : 
      51              :   /// Creates a backend scoring against [profiles] (language code -> ranked
      52              :   /// n-gram list). Defaults to the generated 58-language profile set.
      53            3 :   NgramBackend([Map<String, List<String>>? profiles])
      54              :     : _profiles = profiles ?? ngramProfiles;
      55              : 
      56            1 :   @override
      57            3 :   Set<String> get supportedLanguages => _profiles.keys.toSet();
      58              : 
      59            3 :   @override
      60              :   List<LanguageGuess> score(String text) {
      61            3 :     final queryNgrams = extractRankedNgrams(text, limit: ngramProfileSize);
      62            9 :     if (queryNgrams.isEmpty || _profiles.isEmpty) return const [];
      63              : 
      64            3 :     final distances = <String, int>{};
      65            9 :     for (final entry in _profiles.entries) {
      66           12 :       distances[entry.key] = _distance(queryNgrams, entry.value);
      67              :     }
      68              : 
      69           12 :     final minDistance = distances.values.reduce((a, b) => a < b ? a : b);
      70           12 :     final maxDistance = distances.values.reduce((a, b) => a > b ? a : b);
      71            3 :     final range = maxDistance - minDistance;
      72              : 
      73            3 :     return [
      74            3 :       for (final entry in distances.entries)
      75            3 :         LanguageGuess(
      76            3 :           entry.key,
      77           15 :           range == 0 ? 1.0 : 1.0 - (entry.value - minDistance) / range,
      78              :         ),
      79              :     ];
      80              :   }
      81              : 
      82              :   /// Sums, for each n-gram in [queryNgrams], the absolute rank difference
      83              :   /// against its position in [profile] — or [ngramProfileSize] if [profile]
      84              :   /// doesn't contain it at all.
      85            3 :   int _distance(List<String> queryNgrams, List<String> profile) {
      86            3 :     final profileRank = <String, int>{
      87           15 :       for (var i = 0; i < profile.length; i++) profile[i]: i,
      88              :     };
      89              : 
      90              :     var total = 0;
      91            9 :     for (var rank = 0; rank < queryNgrams.length; rank++) {
      92            6 :       final profileIndex = profileRank[queryNgrams[rank]];
      93            3 :       total += profileIndex == null
      94              :           ? ngramProfileSize
      95            6 :           : (rank - profileIndex).abs();
      96              :     }
      97              :     return total;
      98              :   }
      99              : }