1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
package com.yahoo.language.sentencepiece;
/**
* SentencePiece algorithm implementation
*
* @author bratseth
*/
class SentencePieceAlgorithm {
// TODO: Support characters beyond BMP
static final char spaceSymbol = '▁';
private final boolean collapseUnknowns;
private final Scoring scoring;
SentencePieceAlgorithm(boolean collapseUnknowns, Scoring scoring) {
this.collapseUnknowns = collapseUnknowns;
this.scoring = scoring;
}
public <RESULTTYPE> void segment(String input, ResultBuilder<RESULTTYPE> resultBuilder, Model model) {
SegmentEnd[] segmentEnds = new SegmentEnd[input.length() + 1];
segmentEnds[0] = new SegmentEnd(TokenType.unknown, 0, 0, 0, 0);
int start = 0;
while (start < input.length()) { // segment from this position to the end of the text
Trie.Node node = model.tokens.root;
int characterPosition = start;
while (node != null && characterPosition < input.length()) { // traverse the trie one character at the time from this position
node = node.children.get(input.charAt(characterPosition++));
int length = characterPosition - start;
if (node != null && node.isToken() && node.type != TokenType.unused) {
float score = node.type == TokenType.userDefined ? (length * model.maxScore - 0.1f) : node.score;
addSegment(TokenType.text, node.id, start, characterPosition, score, segmentEnds);
}
else if (length == 1) { // add an 'unknown' length 1 token to make the next position reachable
addSegment(TokenType.unknown, 0, start, start + 1, model.minScore - 10.0f, segmentEnds);
}
}
start++;
}
resultBuilder.build(input, segmentEnds, collapseUnknowns);
}
private void addSegment(TokenType type, int id, int start, int end, float score, SegmentEnd[] segmentEnds) {
if (segmentEnds[end] == null ||
segmentEnds[start].scoreWith(score) > segmentEnds[end].score()) {
segmentEnds[end] = new SegmentEnd(type, id,
segmentEnds[start].pathScoreSum + score,
segmentEnds[start].pathSegmentCount + 1,
start);
}
}
final class SegmentEnd {
final TokenType type;
final int id;
final float pathScoreSum;
final int pathSegmentCount;
final int segmentStart;
SegmentEnd(TokenType type, int id, float pathScoreSum, int pathSegmentCount, int segmentStart) {
this.type = type;
this.id = id;
this.pathScoreSum = pathScoreSum;
this.pathSegmentCount = pathSegmentCount;
this.segmentStart = segmentStart;
}
public float score() {
switch (scoring) {
case fewestSegments: return 1f / pathSegmentCount * 10_000_000 + pathScoreSum;
case highestScore: return pathScoreSum;
default : throw new IllegalArgumentException("Unknown scoring " + scoring);
}
}
public float scoreWith(float additionalSegmentScore) {
switch (scoring) {
case fewestSegments: return 1f / (pathSegmentCount + 1) * 10_000_000 + (pathScoreSum + additionalSegmentScore );
case highestScore: return pathScoreSum + additionalSegmentScore;
default : throw new IllegalArgumentException("Unknown scoring " + scoring);
}
}
}
}
|
