SPB Git

Repository Public

Repetition.swift 13.2 KB 215 lines swift

1// ORIX Docs2// File: Packages/ORIXDocsKit/Sources/DocAudit/Repetition.swift3// Description: Repeated wording: over-used content words (by lemma) and repeated phrases inside a sliding window of words.4//5// Author: Simon-Pierre Boucher6// Contact: contact@spboucher.ai7import Foundation8import NaturalLanguage9import DocModel1011extension ResearchAssistant {12    /// Thresholds of `repeatedWording`.13    public struct RepetitionOptions: Sendable {14        /// A content word is over-used when its lemma occurs at least `minCount` times within `window` consecutive words.15        public var window: Int16        public var minCount: Int17        /// A phrase of at least four words (two of them content words) is repeated when it occurs twice within `phraseWindow` words;18        /// a three-word phrase needs three occurrences.19        public var phraseWindow: Int20        public var maxFindings: Int21        public init(window: Int = 100, minCount: Int = 6, phraseWindow: Int = 250, maxFindings: Int = 50) {22            self.window = window; self.minCount = minCount; self.phraseWindow = phraseWindow; self.maxFindings = maxFindings23        }24    }2526    /// Over-used content words and repeated phrases of the body text (tables included, headings and code excluded).27    /// Words are grouped by lemma (`NLTagger`, language `language` or the document language) so "estimate" and "estimates" count28    /// together; when no lemma is available the lower-cased word is used. Stop words never count.29    public static func repeatedWording(in doc: DocumentModel, language: String?) -> [RepetitionFinding] {30        repeatedWording(in: doc, language: language, options: RepetitionOptions())31    }3233    public static func repeatedWording(in doc: DocumentModel, language: String?, options: RepetitionOptions) -> [RepetitionFinding] {34        struct Word { var form: String; var paragraph: Int; var range: NSRange }35        let lang = (language ?? doc.meta.language).lowercased()36        let french = lang.hasPrefix("fr")37        let stop = french ? StopWords.french : (lang.hasPrefix("en") ? StopWords.english : StopWords.english.union(StopWords.french))3839        var refs: [ParagraphRef] = []40        var texts: [String] = []41        var words: [Word] = []42        var levels = HeadingLevels(doc)43        doc.forEachBodyParagraph { p, path in44            if p.style == StyleID.code || levels.level(p) > 0 { return }45            let text = Scan.maskedText(p)46            let ns = text as NSString47            guard ns.length > 0 else { return }48            let index = refs.count49            var any = false50            for r in Scan.wordRanges(ns) {51                let form = ns.substring(with: r).lowercased()52                guard let first = form.unicodeScalars.first, first.properties.isAlphabetic || first.properties.numericType != nil else { continue }53                words.append(Word(form: form, paragraph: index, range: r))54                any = true55            }56            if any { refs.append(ParagraphRef(story: .body, path: path, paragraph: p)); texts.append(text) }57        }58        guard words.count >= 3 else { return [] }5960        func isContent(_ form: String) -> Bool {61            guard form.count >= 4, !stop.contains(form) else { return false }62            return form.unicodeScalars.allSatisfy { $0.properties.isAlphabetic || $0 == "-" || $0 == "'" || $0 == "’" }63        }64        let content = words.map { isContent($0.form) }65        // Inside a phrase any word of three letters or more that is not a stop word carries meaning ("end", "day").66        let phraseContent = words.map { w in w.form.count >= 3 && !stop.contains(w.form) && w.form.unicodeScalars.contains { $0.properties.isAlphabetic } }67        let lemmas = Lemmatizer.lemmas(of: Set(words.indices.filter { content[$0] }.map { words[$0].form }), language: lang)68        let trails = HeadingTrails(doc)69        func hit(_ id: String, _ w: Int, length: Int = 1) -> Hit {70            let last = words[w + length - 1]71            let range = words[w].range.location..<(last.range.location + last.range.length)72            let ref = refs[words[w].paragraph]73            return Hit(id: id, documentName: doc.meta.title, story: .body, path: ref.path, range: range,74                       context: Scan.context(texts[words[w].paragraph], around: range, radius: 40), headingTrail: trails.trail(ofBlock: ref.path.block))75        }7677        var findings: [(first: Int, finding: RepetitionFinding)] = []7879        // 1. Phrases. Four-word phrases first (extended to their full length), then three-word phrases on what is left.80        var covered = [Bool](repeating: false, count: words.count)81        func phrases(n: Int, minOccurrences: Int) {82            guard words.count >= n else { return }83            var positions: [String: [Int]] = [:]84            for i in 0...(words.count - n) {85                guard words[i].paragraph == words[i + n - 1].paragraph else { continue }86                var contentWords = 087                for k in i..<(i + n) where phraseContent[k] { contentWords += 1 }88                guard contentWords >= 2 else { continue }89                positions[(i..<(i + n)).map { words[$0].form }.joined(separator: " "), default: []].append(i)90            }91            for i in 0...(words.count - n) where !covered[i] {92                guard words[i].paragraph == words[i + n - 1].paragraph else { continue }93                let key = (i..<(i + n)).map { words[$0].form }.joined(separator: " ")94                guard let all = positions[key], all.count >= minOccurrences else { continue }95                // Non-overlapping occurrences starting at i, inside the window.96                var occ: [Int] = [i]97                for p in all where p >= occ.last! + n && p - i <= options.phraseWindow && !covered[p] { occ.append(p) }98                guard occ.count >= minOccurrences else { continue }99                // Extend the phrase to the left, then to the right, while every occurrence agrees.100                var back = 0101                while true {102                    let q0 = i - back - 1103                    var ok = q0 >= 0 && words[q0].paragraph == words[i].paragraph && !covered[q0]104                    if ok {105                        for (k, p) in occ.enumerated() {106                            let q = p - back - 1107                            if q < 0 || words[q].paragraph != words[p].paragraph || words[q].form != words[q0].form || covered[q] || (k > 0 && q < occ[k - 1] + n) {108                                ok = false109                                break110                            }111                        }112                    }113                    if !ok { break }114                    back += 1115                }116                var length = n117                while true {118                    let q0 = i + length119                    var ok = q0 < words.count && words[q0].paragraph == words[i].paragraph120                    if ok {121                        for (k, p) in occ.enumerated() {122                            let q = p + length123                            if q >= words.count || words[q].paragraph != words[p].paragraph || words[q].form != words[q0].form || (k + 1 < occ.count && q >= occ[k + 1]) {124                                ok = false125                                break126                            }127                        }128                    }129                    if !ok { break }130                    length += 1131                }132                // A phrase does not end on a stop word ("… of the trading day the").133                while length > n && stop.contains(words[i + length - 1].form) { length -= 1 }134                for p in occ { for k in (p - back)..<min(words.count, p + length) { covered[k] = true } }135                let start = i - back, total = length + back136                let text = (start..<(start + total)).map { words[$0].form }.joined(separator: " ")137                let id = "phrase#\(refs[words[start].paragraph].path.sortKey)#\(words[start].range.location)"138                findings.append((start, RepetitionFinding(id: id, kind: .phrase, text: text, count: occ.count, span: occ.last! + length - start,139                                                          occurrences: occ.enumerated().map { hit("\(id)#\($0.offset)", $0.element - back, length: total) })))140            }141        }142        phrases(n: 4, minOccurrences: 2)143        phrases(n: 3, minOccurrences: 3)144145        // 2. Over-used content words: densest window per lemma.146        var byLemma: [String: [Int]] = [:]147        for i in words.indices where content[i] { byLemma[lemmas[words[i].form] ?? words[i].form, default: []].append(i) }148        for (lemma, pos) in byLemma where pos.count >= options.minCount && !stop.contains(lemma) {149            var bestLo = 0, bestCount = 0150            var lo = 0151            for hi in pos.indices {152                while pos[hi] - pos[lo] >= options.window { lo += 1 }153                if hi - lo + 1 > bestCount { bestCount = hi - lo + 1; bestLo = lo }154            }155            guard bestCount >= options.minCount else { continue }156            let occ = Array(pos[bestLo..<(bestLo + bestCount)])157            // Occurrences that are all part of one reported phrase are already covered.158            if occ.allSatisfy({ covered[$0] }) { continue }159            let id = "word#\(lemma)"160            findings.append((occ[0], RepetitionFinding(id: id, kind: .word, text: lemma, count: bestCount, span: occ.last! - occ[0] + 1,161                                                       occurrences: occ.enumerated().map { hit("\(id)#\($0.offset)", $0.element) })))162        }163164        findings.sort { ($0.first, $0.finding.id) < ($1.first, $1.finding.id) }165        return Array(findings.prefix(options.maxFindings).map(\.finding))166    }167}168169/// Context-free lemmas of a set of words, through one `NLTagger` pass.170enum Lemmatizer {171    static func lemmas(of forms: Set<String>, language: String) -> [String: String] {172        guard !forms.isEmpty else { return [:] }173        let sorted = forms.sorted()174        let text = sorted.joined(separator: "\n")175        let tagger = NLTagger(tagSchemes: [.lemma])176        tagger.string = text177        let nl = NLLanguage(rawValue: String(language.prefix(2)))178        tagger.setLanguage(nl, range: text.startIndex..<text.endIndex)179        // Each line is one word: a token that covers its whole line gives that word's lemma.180        var out: [String: String] = [:]181        tagger.enumerateTags(in: text.startIndex..<text.endIndex, unit: .word, scheme: .lemma, options: [.omitWhitespace, .omitPunctuation]) { tag, range in182            guard let tag else { return true }183            let token = String(text[range])184            let lemma = tag.rawValue.lowercased()185            if !lemma.isEmpty, forms.contains(token), out[token] == nil { out[token] = lemma }186            return true187        }188        return out189    }190}191192enum StopWords {193    static let english: Set<String> = Set("""194    a about above after again against all also although am among an and any are aren't as at be because been before being below between both but by can195    cannot could couldn't did didn't do does doesn't doing don't down during each either even ever every few for from further had hadn't has hasn't have196    haven't having he her here hers herself him himself his how however i if in into is isn't it its itself just least less let many may me might more197    most much must my myself neither no nor not now of off often on once one only or other others ought our ours ourselves out over own per rather same198    shall she should shouldn't since so some such than that the their theirs them themselves then there therefore these they this those though through199    thus to too toward towards under until up upon us very was wasn't we were weren't what when where whereas whether which while who whom whose why will200    with within without would wouldn't yet you your yours yourself yourselves been being two three first second new make made makes use used uses using201    """.split(whereSeparator: { $0.isWhitespace }).map(String.init))202203    static let french: Set<String> = Set("""204    a à afin ai aie ainsi alors après assez au aucun aucune aujourd'hui auprès auquel aussi autant autre autres aux auxquelles auxquels avait avant avec205    avoir ayant bien car ce ceci cela celle celles celui cependant certain certaine certaines certains ces cet cette ceux chacun chaque chez comme206    comment contre d dans de dedans dehors déjà depuis des dès desquelles desquels deux devant doit donc dont du duquel durant elle elles en encore207    entre envers est et étaient étais était étant été être eu eux fait faire fois font furent grâce hors ici il ils j je jusqu jusque l la là laquelle208    le lequel les lesquelles lesquels leur leurs lors lorsque lui ma mais malgré me même mêmes mes mien mienne moi moins mon ne ni non nos notre nous209    on ont or ou où par parce parfois parmi pas pendant peu peut peuvent plus plusieurs plutôt pour pourquoi pourtant près puis puisque qu quand que210    quel quelle quelles quelque quelques quels qui quoi quoique sa sans sauf se selon sera seront ses si sien sienne soi soit sommes son sont sous211    souvent suis sur ta tandis tant te tel telle telles tels tes toi ton tous tout toute toutes très trop tu un une vers via voici voilà vos votre vous212    y cette celui-ci celle-ci ainsi alors aussi avoir être faire deux trois premier première nouveau nouvelle213    """.split(whereSeparator: { $0.isWhitespace }).map(String.init))214}215
Files main
Menu

Theme