sudachi/
sentence_detector.rs

1/*
2 * Copyright (c) 2021-2026 Works Applications Co., Ltd.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *     http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17use std::cmp::Ordering;
18use std::sync::OnceLock;
19
20use crate::dic::lexicon_set::LexiconSet;
21use crate::prelude::*;
22
23/// A checker for words that cross boundaries
24pub struct NonBreakChecker<'a> {
25    lexicon: &'a LexiconSet<'a>,
26    pub bos: usize,
27}
28impl<'a> NonBreakChecker<'a> {
29    pub fn new(lexicon: &'a LexiconSet<'a>) -> Self {
30        NonBreakChecker { lexicon, bos: 0 }
31    }
32}
33
34impl NonBreakChecker<'_> {
35    /// Returns whether there is a word that crosses the boundary
36    fn has_non_break_word(&self, input: &str, length: usize) -> bool {
37        // assume that SentenceDetector::get_eos called with self.input[self.bos..]
38        let eos_byte = self.bos + length;
39        if eos_byte > input.len() || !input.is_char_boundary(eos_byte) {
40            return false;
41        }
42
43        let input_bytes = input.as_bytes();
44        const LOOKUP_BYTE_LENGTH: usize = 10 * 3; // 10 Japanese characters in UTF-8
45        let mut lookup_start = eos_byte.saturating_sub(LOOKUP_BYTE_LENGTH);
46        while lookup_start < eos_byte && !input.is_char_boundary(lookup_start) {
47            lookup_start += 1;
48        }
49
50        for (relative, _) in input[lookup_start..eos_byte].char_indices() {
51            let i = lookup_start + relative;
52            if let Some(result) = self.lexicon.check_prefix_ends(input_bytes, i, |end_byte| {
53                // handling cases like モーニング娘。
54                match end_byte.cmp(&eos_byte) {
55                    // end is after than boundary candidate, this boundary is bad
56                    Ordering::Greater => Some(true),
57                    // end is on boundary candidate,
58                    // check that there are more than one character in the matched word
59                    Ordering::Equal => Some(input[i..].chars().nth(1).is_some()),
60                    _ => None,
61                }
62            }) {
63                return result;
64            }
65        }
66        false
67    }
68}
69
70const DEFAULT_LIMIT: usize = 4096;
71
72/// A sentence boundary detector
73pub struct SentenceDetector {
74    // The maximum number of characters processed at once
75    limit: usize,
76}
77
78impl Default for SentenceDetector {
79    fn default() -> Self {
80        Self::new()
81    }
82}
83
84impl SentenceDetector {
85    pub fn new() -> Self {
86        SentenceDetector {
87            limit: DEFAULT_LIMIT,
88        }
89    }
90    pub fn with_limit(limit: usize) -> Self {
91        SentenceDetector { limit }
92    }
93
94    /// Returns the byte index of the detected end of the sentence.
95    ///
96    /// If NonBreakChecker is given, it is used to determine if there is a
97    /// word that crosses the detected boundary, and if so, the next boundary is
98    /// returned.
99    ///
100    /// If there is no boundary, this returns a relatively harmles boundary as a
101    /// negative value.
102    ///
103    /// # Examples
104    ///
105    /// ```
106    /// let sd = sudachi::sentence_detector::SentenceDetector::new();
107    /// assert_eq!(12, sd.get_eos("あいう。えお", None).unwrap());
108    /// assert_eq!(-15, sd.get_eos("あいうえお", None).unwrap());
109    /// ```
110    pub fn get_eos(&self, input: &str, checker: Option<&NonBreakChecker>) -> SudachiResult<isize> {
111        if input.is_empty() {
112            return Ok(0);
113        }
114
115        let (s, input_exceeds_limit) = limited_prefix(input, self.limit);
116
117        if let Some(eos) = find_sentence_boundary(s, input, checker) {
118            return Ok(eos as isize);
119        }
120
121        if input_exceeds_limit {
122            // search the final whitespace as a provisional split.
123            if let Some(end) = legacy_whitespace_end(s) {
124                return Ok(-(end as isize));
125            }
126        }
127
128        Ok(-(s.len() as isize))
129    }
130}
131
132#[inline]
133fn limited_prefix(input: &str, limit: usize) -> (&str, bool) {
134    if input.len() <= limit {
135        return (input, false);
136    }
137
138    match input.char_indices().nth(limit) {
139        Some((idx, _)) => (&input[..idx], true),
140        None => (input, false),
141    }
142}
143
144fn find_sentence_boundary(
145    limited: &str,
146    original: &str,
147    checker: Option<&NonBreakChecker>,
148) -> Option<usize> {
149    let mut index = 0;
150    let mut previous = None;
151    let mut parenthesis_level = 0usize;
152
153    while index < limited.len() {
154        let c = limited[index..]
155            .chars()
156            .next()
157            .expect("valid char boundary");
158        let next_index = index + c.len_utf8();
159
160        if is_open_parenthesis(c) {
161            parenthesis_level += 1;
162            previous = Some(c);
163            index = next_index;
164            continue;
165        }
166
167        if is_close_parenthesis(c) {
168            parenthesis_level = parenthesis_level.saturating_sub(1);
169            previous = Some(c);
170            index = next_index;
171            continue;
172        }
173
174        if let Some(candidate_end) = sentence_candidate_end(limited, index, c, previous) {
175            if parenthesis_level == 0 {
176                let mut eos = candidate_end;
177                if eos < limited.len() {
178                    eos += prohibited_bos_len(&limited[eos..]);
179                }
180
181                if !is_itemize_header(limited) && !continues_phrase(limited, eos) {
182                    if let Some(ck) = checker {
183                        if ck.has_non_break_word(original, eos) {
184                            previous = limited[..candidate_end].chars().next_back();
185                            index = candidate_end;
186                            continue;
187                        }
188                    }
189                    return Some(eos);
190                }
191            }
192
193            previous = limited[..candidate_end].chars().next_back();
194            index = candidate_end;
195            continue;
196        }
197
198        previous = Some(c);
199        index = next_index;
200    }
201
202    None
203}
204
205fn sentence_candidate_end(s: &str, index: usize, c: char, previous: Option<char>) -> Option<usize> {
206    if is_sentence_period(c) {
207        return Some(consume_trailing_break_chars(s, index + c.len_utf8()));
208    }
209
210    if c == '・' {
211        return cdots_candidate_end(s, index);
212    }
213
214    if is_dot(c) {
215        let next_index = index + c.len_utf8();
216        let previous_blocks = previous.map(is_alphabet_or_number).unwrap_or(false);
217        let next_blocks = s[next_index..]
218            .chars()
219            .next()
220            .map(|next| is_alphabet_or_number(next) || is_comma(next))
221            .unwrap_or(false);
222
223        if !previous_blocks && !next_blocks {
224            return Some(consume_trailing_break_chars(s, next_index));
225        }
226    }
227
228    if c == '<' {
229        return br_sequence_end(s, index);
230    }
231
232    None
233}
234
235fn cdots_candidate_end(s: &str, index: usize) -> Option<usize> {
236    let mut count = 0;
237    let mut end = index;
238    while let Some(c) = s[end..].chars().next() {
239        if c != '・' {
240            break;
241        }
242        count += 1;
243        end += c.len_utf8();
244    }
245
246    if count >= 3 {
247        Some(consume_trailing_break_chars(s, end))
248    } else {
249        None
250    }
251}
252
253fn br_sequence_end(s: &str, index: usize) -> Option<usize> {
254    let mut count = 0;
255    let mut end = index;
256    while let Some(len) = br_tag_len(&s[end..]) {
257        count += 1;
258        end += len;
259    }
260
261    if count >= 2 {
262        Some(end)
263    } else {
264        None
265    }
266}
267
268#[inline]
269fn br_tag_len(s: &str) -> Option<usize> {
270    if s.starts_with("<br>") || s.starts_with("<BR>") {
271        Some(4)
272    } else {
273        None
274    }
275}
276
277fn consume_trailing_break_chars(s: &str, mut index: usize) -> usize {
278    while let Some(c) = s[index..].chars().next() {
279        if !is_dot(c) && !is_sentence_period(c) {
280            break;
281        }
282        index += c.len_utf8();
283    }
284    index
285}
286
287/// Returns a byte length of chars at the beginning of str, which cannot be a bos.
288fn prohibited_bos_len(s: &str) -> usize {
289    let mut end = 0;
290    for (index, c) in s.char_indices() {
291        if !is_close_parenthesis(c) && !is_comma(c) && !is_sentence_period(c) {
292            break;
293        }
294        end = index + c.len_utf8();
295    }
296    end
297}
298
299fn continues_phrase(s: &str, eos: usize) -> bool {
300    if eos >= s.len() {
301        return false;
302    }
303
304    let last = s[..eos]
305        .chars()
306        .next_back()
307        .expect("eos is after a boundary candidate");
308    let rest = &s[eos..];
309    if is_quote_marker(last)
310        && (rest.starts_with("と") || rest.starts_with("っ") || rest.starts_with("です"))
311    {
312        return true;
313    }
314
315    let next = rest.chars().next().expect("eos is a valid char boundary");
316    (next == 'と' || next == 'や' || next == 'の') && ends_with_itemize_header(&s[..eos])
317}
318
319fn is_itemize_header(s: &str) -> bool {
320    let mut chars = s.chars();
321    let Some(first) = chars.next() else {
322        return false;
323    };
324    let Some(second) = chars.next() else {
325        return false;
326    };
327    chars.next().is_none() && is_alphabet_or_number(first) && is_dot(second)
328}
329
330fn ends_with_itemize_header(s: &str) -> bool {
331    let mut chars = s.chars().rev();
332    let Some(last) = chars.next() else {
333        return false;
334    };
335    let Some(previous) = chars.next() else {
336        return false;
337    };
338    is_dot(last) && is_alphabet_or_number(previous)
339}
340
341fn legacy_whitespace_end(s: &str) -> Option<usize> {
342    static SPACES: OnceLock<regex::Regex> = OnceLock::new();
343    SPACES
344        .get_or_init(|| regex::Regex::new(r".+\s+").unwrap())
345        .find(s)
346        .map(|mat| mat.end())
347}
348
349#[inline]
350fn is_sentence_period(c: char) -> bool {
351    matches!(c, '。' | '？' | '！' | '♪' | '…' | '?' | '!')
352}
353
354#[inline]
355fn is_dot(c: char) -> bool {
356    matches!(c, '.' | '．')
357}
358
359#[inline]
360fn is_comma(c: char) -> bool {
361    matches!(c, ',' | '，' | '、')
362}
363
364#[inline]
365fn is_alphabet_or_number(c: char) -> bool {
366    c.is_ascii_alphanumeric()
367        || matches!(
368            c,
369            'ａ'..='ｚ'
370                | 'Ａ'..='Ｚ'
371                | '０'..='９'
372                | '〇'
373                | '一'
374                | '二'
375                | '三'
376                | '四'
377                | '五'
378                | '六'
379                | '七'
380                | '八'
381                | '九'
382                | '十'
383                | '百'
384                | '千'
385                | '万'
386                | '億'
387                | '兆'
388        )
389}
390
391#[inline]
392fn is_open_parenthesis(c: char) -> bool {
393    matches!(
394        c,
395        '(' | '{' | '｛' | '[' | '（' | '「' | '【' | '『' | '［' | '≪' | '〔' | '“' | '"'
396    )
397}
398
399#[inline]
400fn is_close_parenthesis(c: char) -> bool {
401    matches!(
402        c,
403        ')' | '}' | ']' | '）' | '」' | '｝' | '】' | '』' | '］' | '〕' | '≫' | '”' | '"'
404    )
405}
406
407#[inline]
408fn is_quote_marker(c: char) -> bool {
409    matches!(c, '！' | '？' | '!' | '?') || is_close_parenthesis(c)
410}
411
412#[cfg(test)]
413mod tests {
414    use super::*;
415
416    #[test]
417    fn get_eos() {
418        let sd = SentenceDetector::new();
419        assert_eq!(sd.get_eos("あいうえお。", None).unwrap(), 18);
420        assert_eq!(sd.get_eos("あいう。えお。", None).unwrap(), 12);
421        assert_eq!(sd.get_eos("あいう。。えお。", None).unwrap(), 15);
422        assert_eq!(sd.get_eos("あいうえお", None).unwrap(), -15);
423        assert_eq!(sd.get_eos("あいう えお。", None).unwrap(), 19);
424        assert_eq!(sd.get_eos("あいう えお", None).unwrap(), -16);
425        assert_eq!(sd.get_eos("", None).unwrap(), 0);
426    }
427
428    #[test]
429    fn get_eos_with_limit() {
430        let sd = SentenceDetector::with_limit(5);
431        assert_eq!(sd.get_eos("あいうえおか。", None).unwrap(), -15);
432        assert_eq!(sd.get_eos("あい。うえお。", None).unwrap(), 9);
433        assert_eq!(sd.get_eos("あいうえ", None).unwrap(), -12);
434        assert_eq!(sd.get_eos("あい うえお", None).unwrap(), -7);
435        assert_eq!(sd.get_eos("あ い うえお", None).unwrap(), -8);
436    }
437
438    #[test]
439    fn get_eos_with_multibyte_limit_boundary() {
440        let sd = SentenceDetector::with_limit(4);
441        assert_eq!(sd.get_eos("あいう。", None).unwrap(), 12);
442        assert_eq!(sd.get_eos("あいうえ。", None).unwrap(), -12);
443        assert_eq!(sd.get_eos("あい うえ。", None).unwrap(), -7);
444    }
445
446    #[test]
447    fn get_eos_with_limit_multiline_whitespace_legacy_behavior() {
448        let sd = SentenceDetector::with_limit(5);
449        assert_eq!(sd.get_eos("a\n b c d", None).unwrap(), -3);
450    }
451
452    #[test]
453    fn get_eos_with_period() {
454        let sd = SentenceDetector::new();
455        assert_eq!(sd.get_eos("あいう.えお", None).unwrap(), 10);
456        assert_eq!(sd.get_eos("3.141", None).unwrap(), -5);
457        assert_eq!(sd.get_eos("四百十.〇", None).unwrap(), -13);
458    }
459
460    #[test]
461    fn get_eos_with_many_periods() {
462        let sd = SentenceDetector::new();
463        assert_eq!(sd.get_eos("あいうえお!??", None).unwrap(), 18);
464    }
465
466    #[test]
467    fn get_eos_with_cdots() {
468        let sd = SentenceDetector::new();
469        assert_eq!(sd.get_eos("あ・・・い", None).unwrap(), 12);
470        assert_eq!(sd.get_eos("あ・・い", None).unwrap(), -12);
471        assert_eq!(sd.get_eos("あ・・・?!い", None).unwrap(), 14);
472    }
473
474    #[test]
475    fn get_eos_with_br_tags() {
476        let sd = SentenceDetector::new();
477        assert_eq!(sd.get_eos("あ<br><br>い", None).unwrap(), 11);
478        assert_eq!(sd.get_eos("あ<BR><BR>い", None).unwrap(), 11);
479        assert_eq!(sd.get_eos("あ<br><BR>い", None).unwrap(), 11);
480        assert_eq!(sd.get_eos("あ<br>い", None).unwrap(), -10);
481    }
482
483    #[test]
484    fn get_eos_with_parentheses() {
485        let sd = SentenceDetector::new();
486        assert_eq!(sd.get_eos("あ（いう。え）お", None).unwrap(), -24);
487        assert_eq!(sd.get_eos("（あ（いう）。え）お", None).unwrap(), -30);
488        assert_eq!(sd.get_eos("あ（いう）。えお", None).unwrap(), 18);
489    }
490
491    #[test]
492    fn get_eos_with_ascii_quote_legacy_behavior() {
493        let sd = SentenceDetector::new();
494        assert_eq!(sd.get_eos("\"あ。\"", None).unwrap(), -8);
495        assert_eq!(sd.get_eos("あ。\"です。", None).unwrap(), -16);
496        assert_eq!(sd.get_eos("あ。\")え。", None).unwrap(), 8);
497    }
498
499    #[test]
500    fn get_eos_with_itemize_header() {
501        let sd = SentenceDetector::new();
502        assert_eq!(sd.get_eos("1. あいう。えお", None).unwrap(), 15);
503    }
504
505    #[test]
506    fn get_eos_with_prohibited_bos() {
507        let sd = SentenceDetector::new();
508        assert_eq!(sd.get_eos("あいう?えお", None).unwrap(), 10);
509        assert_eq!(sd.get_eos("あいう?)えお", None).unwrap(), 11);
510        assert_eq!(sd.get_eos("あいう?,えお", None).unwrap(), 11);
511    }
512
513    #[test]
514    fn get_eos_with_continuous_phrase() {
515        let sd = SentenceDetector::new();
516        assert_eq!(sd.get_eos("あいう?です。", None).unwrap(), 19);
517        assert_eq!(sd.get_eos("あいう?って。", None).unwrap(), 19);
518        assert_eq!(sd.get_eos("あいう?という。", None).unwrap(), 22);
519        assert_eq!(sd.get_eos("あいう?の？です。", None).unwrap(), 10);
520
521        assert_eq!(sd.get_eos("1.と2.が。", None).unwrap(), 13);
522        assert_eq!(sd.get_eos("1.やb.から。", None).unwrap(), 16);
523        assert_eq!(sd.get_eos("1.の12.が。", None).unwrap(), 14);
524    }
525}
sudachi/sentence_detector.rs

sudachi/
sentence_detector.rs
