1 // Copyright 2011 Google Inc. All Rights Reserved.
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
7 // http://www.apache.org/licenses/LICENSE-2.0
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.
15 package com.hughes.android.dictionary.engine;
17 import java.io.DataInput;
18 import java.io.DataOutput;
19 import java.io.IOException;
20 import java.io.PrintStream;
21 import java.io.RandomAccessFile;
22 import java.nio.channels.FileChannel;
23 import java.util.AbstractList;
24 import java.util.ArrayList;
25 import java.util.Collection;
26 import java.util.Collections;
27 import java.util.Comparator;
28 import java.util.EnumMap;
29 import java.util.HashMap;
30 import java.util.HashSet;
31 import java.util.List;
34 import java.util.concurrent.atomic.AtomicBoolean;
35 import java.util.regex.Pattern;
37 import com.hughes.android.dictionary.DictionaryInfo;
38 import com.hughes.android.dictionary.DictionaryInfo.IndexInfo;
39 import com.hughes.android.dictionary.engine.RowBase.RowKey;
40 import com.hughes.util.CachingList;
41 import com.hughes.util.StringUtil;
42 import com.hughes.util.TransformingList;
43 import com.hughes.util.raf.RAFList;
44 import com.hughes.util.raf.RAFSerializable;
45 import com.hughes.util.raf.RAFSerializer;
46 import com.hughes.util.raf.SerializableSerializer;
47 import com.hughes.util.raf.UniformRAFList;
48 import com.ibm.icu.text.Transliterator;
50 public final class Index implements RAFSerializable<Index> {
52 private static final int CACHE_SIZE = 5000;
54 public final Dictionary dict;
56 public final String shortName; // Typically the ISO code for the language.
57 public final String longName;
59 // persisted: tells how the entries are sorted.
60 public final Language sortLanguage;
61 public final String normalizerRules;
63 // Built from the two above.
64 private Transliterator normalizer;
67 public final List<IndexEntry> sortedIndexEntries;
70 public final Set<String> stoplist;
75 public final List<RowBase> rows;
76 public final boolean swapPairEntries;
79 @SuppressWarnings("WeakerAccess")
80 public int mainTokenCount = -1;
82 // --------------------------------------------------------------------------
84 public Index(final Dictionary dict, final String shortName, final String longName,
85 final Language sortLanguage, final String normalizerRules,
86 final boolean swapPairEntries, final Set<String> stoplist) {
88 this.shortName = shortName;
89 this.longName = longName;
90 this.sortLanguage = sortLanguage;
91 this.normalizerRules = normalizerRules;
92 this.swapPairEntries = swapPairEntries;
93 sortedIndexEntries = new ArrayList<>();
94 this.stoplist = stoplist;
95 rows = new ArrayList<>();
101 * Deferred initialization because it can be slow.
103 @SuppressWarnings("WeakerAccess")
104 public synchronized Transliterator normalizer() {
105 if (normalizer == null) {
106 normalizer = TransliteratorManager.get(normalizerRules);
112 * Note that using this comparator probably involves doing too many text
115 @SuppressWarnings("WeakerAccess")
116 public NormalizeComparator getSortComparator() {
117 return new NormalizeComparator(normalizer(), sortLanguage.getCollator(), dict.dictFileVersion);
120 public Index(final Dictionary dict, final FileChannel inp, final DataInput raf) throws IOException {
122 shortName = raf.readUTF();
123 longName = raf.readUTF();
124 final String languageCode = raf.readUTF();
125 sortLanguage = Language.lookup(languageCode);
126 normalizerRules = raf.readUTF();
127 swapPairEntries = raf.readBoolean();
128 if (dict.dictFileVersion >= 2) {
129 mainTokenCount = raf.readInt();
131 sortedIndexEntries = CachingList.create(
132 RAFList.create(inp, new IndexEntrySerializer(dict.dictFileVersion == 6 ? inp : null), inp.position(),
133 dict.dictFileVersion, dict.dictInfo + " idx " + languageCode + ": "), CACHE_SIZE, true);
134 if (dict.dictFileVersion >= 7) {
135 int count = StringUtil.readVarInt(raf);
136 stoplist = new HashSet<>(count);
137 for (int i = 0; i < count; ++i) {
138 stoplist.add(raf.readUTF());
140 } else if (dict.dictFileVersion >= 4) {
141 stoplist = new SerializableSerializer<Set<String>>().read(raf);
143 stoplist = Collections.emptySet();
145 rows = CachingList.create(
146 UniformRAFList.create(inp, new RowBase.Serializer(this), inp.position()),
151 public void write(final DataOutput out) throws IOException {
152 RandomAccessFile raf = (RandomAccessFile)out;
153 raf.writeUTF(shortName);
154 raf.writeUTF(longName);
155 raf.writeUTF(sortLanguage.getIsoCode());
156 raf.writeUTF(normalizerRules);
157 raf.writeBoolean(swapPairEntries);
158 raf.writeInt(mainTokenCount);
159 RAFList.write(raf, sortedIndexEntries, new IndexEntrySerializer(null), 32, true);
160 StringUtil.writeVarInt(raf, stoplist.size());
161 for (String i : stoplist) {
164 UniformRAFList.write(raf, rows, new RowBase.Serializer(this), 3 /* bytes per entry */);
167 public void print(final PrintStream out) {
168 for (final RowBase row : rows) {
173 private final class IndexEntrySerializer implements RAFSerializer<IndexEntry> {
174 private final FileChannel ch;
176 IndexEntrySerializer(FileChannel ch) {
181 public IndexEntry read(DataInput raf) throws IOException {
182 return new IndexEntry(Index.this, ch, raf);
186 public void write(DataOutput raf, IndexEntry t) throws IOException {
191 public static final class IndexEntry implements RAFSerializable<Index.IndexEntry> {
192 public final String token;
193 private final String normalizedToken;
194 public final int startRow;
195 final int numRows; // doesn't count the token row!
196 public List<HtmlEntry> htmlEntries;
198 public IndexEntry(final Index index, final String token, final String normalizedToken,
199 final int startRow, final int numRows) {
200 assert token.equals(token.trim());
201 assert token.length() > 0;
203 this.normalizedToken = normalizedToken;
204 this.startRow = startRow;
205 this.numRows = numRows;
206 this.htmlEntries = new ArrayList<>();
209 IndexEntry(final Index index, final FileChannel ch, final DataInput raf) throws IOException {
210 token = raf.readUTF();
211 if (index.dict.dictFileVersion >= 7) {
212 startRow = StringUtil.readVarInt(raf);
213 numRows = StringUtil.readVarInt(raf);
215 startRow = raf.readInt();
216 numRows = raf.readInt();
218 final boolean hasNormalizedForm = raf.readBoolean();
219 normalizedToken = hasNormalizedForm ? raf.readUTF() : token;
220 if (index.dict.dictFileVersion >= 7) {
221 int size = StringUtil.readVarInt(raf);
223 this.htmlEntries = Collections.emptyList();
225 final int[] htmlEntryIndices = new int[size];
226 for (int i = 0; i < size; ++i) {
227 htmlEntryIndices[i] = StringUtil.readVarInt(raf);
229 this.htmlEntries = new AbstractList<HtmlEntry>() {
231 public HtmlEntry get(int i) {
232 return index.dict.htmlEntries.get(htmlEntryIndices[i]);
236 return htmlEntryIndices.length;
240 } else if (index.dict.dictFileVersion >= 6) {
241 this.htmlEntries = CachingList.create(
242 RAFList.create(ch, index.dict.htmlEntryIndexSerializer,
243 ch.position(), index.dict.dictFileVersion,
244 index.dict.dictInfo + " htmlEntries: "), 1, false);
246 this.htmlEntries = Collections.emptyList();
250 public void write(DataOutput raf) throws IOException {
252 StringUtil.writeVarInt(raf, startRow);
253 StringUtil.writeVarInt(raf, numRows);
254 final boolean hasNormalizedForm = !token.equals(normalizedToken);
255 raf.writeBoolean(hasNormalizedForm);
256 if (hasNormalizedForm) {
257 raf.writeUTF(normalizedToken);
259 StringUtil.writeVarInt(raf, htmlEntries.size());
260 for (HtmlEntry e : htmlEntries)
261 StringUtil.writeVarInt(raf, e.index());
264 public String toString() {
265 return String.format("%s@%d(%d)", token, startRow, numRows);
268 String normalizedToken() {
269 return normalizedToken;
273 private static final TransformingList.Transformer<IndexEntry, String> INDEX_ENTRY_TO_TOKEN = new TransformingList.Transformer<IndexEntry, String>() {
275 public String transform(IndexEntry t1) {
280 public IndexEntry findExact(final String exactToken) {
281 final int result = Collections.binarySearch(
282 TransformingList.create(sortedIndexEntries, INDEX_ENTRY_TO_TOKEN), exactToken,
283 getSortComparator());
285 return sortedIndexEntries.get(result);
290 public IndexEntry findInsertionPoint(String token, final AtomicBoolean interrupted) {
291 final int index = findInsertionPointIndex(token, interrupted);
292 return index != -1 ? sortedIndexEntries.get(index) : null;
295 private int compareIdx(String token, final Comparator<Object> sortCollator, int idx) {
296 final IndexEntry entry = sortedIndexEntries.get(idx);
297 return NormalizeComparator.compareWithoutDash(token, entry.normalizedToken(), sortCollator, dict.dictFileVersion);
300 private int findMatchLen(final Comparator<Object> sortCollator, String a, String b) {
302 int end = Math.min(a.length(), b.length());
305 int mid = (start + end + 1) / 2;
306 if (sortCollator.compare(a.substring(0, mid), b.substring(0, mid)) == 0)
314 private int findInsertionPointIndex(String token, final AtomicBoolean interrupted) {
315 token = normalizeToken(token);
318 int end = sortedIndexEntries.size();
320 final Comparator<Object> sortCollator = sortLanguage.getCollator();
321 while (start < end) {
322 final int mid = (start + end) / 2;
323 if (interrupted.get()) {
326 final IndexEntry midEntry = sortedIndexEntries.get(mid);
328 int comp = NormalizeComparator.compareWithoutDash(token, midEntry.normalizedToken(), sortCollator, dict.dictFileVersion);
330 comp = sortCollator.compare(token, midEntry.normalizedToken());
332 return windBackCase(token, mid, interrupted);
333 } else if (comp < 0) {
334 // System.out.println("Upper bound: " + midEntry + ", norm=" +
335 // midEntry.normalizedToken() + ", mid=" + mid);
337 // Hack for robustness if sort order is broken
339 compareIdx(token, sortCollator, mid + 1) > 0 &&
340 compareIdx(token, sortCollator, mid + 2) > 0) {
346 // System.out.println("Lower bound: " + midEntry + ", norm=" +
347 // midEntry.normalizedToken() + ", mid=" + mid);
349 // Hack for robustness if sort order is broken
350 if (mid - 2 >= start &&
351 compareIdx(token, sortCollator, mid - 1) < 0 &&
352 compareIdx(token, sortCollator, mid - 2) < 0) {
360 // if the word before is the better match, move
362 if (start > 0 && start < sortedIndexEntries.size()) {
363 String prev = sortedIndexEntries.get(start - 1).normalizedToken();
364 String next = sortedIndexEntries.get(start).normalizedToken();
365 if (findMatchLen(sortCollator, token, prev) >= findMatchLen(sortCollator, token, next))
369 // If we search for a substring of a string that's in there, return
371 int result = Math.min(start, sortedIndexEntries.size() - 1);
372 result = windBackCase(sortedIndexEntries.get(result).normalizedToken(), result, interrupted);
376 private final int windBackCase(final String token, int result, final AtomicBoolean interrupted) {
377 while (result > 0 && sortedIndexEntries.get(result - 1).normalizedToken().equals(token)) {
379 if (interrupted.get()) {
386 public IndexInfo getIndexInfo() {
387 return new DictionaryInfo.IndexInfo(shortName, sortedIndexEntries.size(), mainTokenCount);
390 private static final int MAX_SEARCH_ROWS = 1000;
392 private final Map<String, Integer> prefixToNumRows = new HashMap<>();
394 private synchronized final int getUpperBoundOnRowsStartingWith(final String normalizedPrefix,
395 final int maxRows, final AtomicBoolean interrupted) {
396 final Integer numRows = prefixToNumRows.get(normalizedPrefix);
397 if (numRows != null) {
400 final int insertionPointIndex = findInsertionPointIndex(normalizedPrefix, interrupted);
403 for (int index = insertionPointIndex; index < sortedIndexEntries.size(); ++index) {
404 if (interrupted.get()) {
407 final IndexEntry indexEntry = sortedIndexEntries.get(index);
408 if (!indexEntry.normalizedToken.startsWith(normalizedPrefix) &&
409 !NormalizeComparator.withoutDash(indexEntry.normalizedToken).startsWith(normalizedPrefix)) {
412 rowCount += indexEntry.numRows + indexEntry.htmlEntries.size();
413 if (rowCount > maxRows) {
414 System.out.println("Giving up, too many words with prefix: " + normalizedPrefix);
418 prefixToNumRows.put(normalizedPrefix, rowCount);
422 public final List<RowBase> multiWordSearch(
423 final String searchText, final List<String> searchTokens,
424 final AtomicBoolean interrupted) {
425 final long startMills = System.currentTimeMillis();
426 final List<RowBase> result = new ArrayList<>();
428 final Set<String> normalizedNonStoplist = new HashSet<>();
430 String bestPrefix = null;
431 int leastRows = Integer.MAX_VALUE;
432 final StringBuilder searchTokensRegex = new StringBuilder();
433 for (int i = 0; i < searchTokens.size(); ++i) {
434 if (interrupted.get()) {
437 final String searchToken = searchTokens.get(i);
438 final String normalized = normalizeToken(searchTokens.get(i));
439 // Normalize them all.
440 searchTokens.set(i, normalized);
442 if (!stoplist.contains(searchToken)) {
443 if (normalizedNonStoplist.add(normalized)) {
444 final int numRows = getUpperBoundOnRowsStartingWith(normalized,
445 MAX_SEARCH_ROWS, interrupted);
446 if (numRows != -1 && numRows < leastRows) {
448 // We really are done here.
449 return Collections.emptyList();
452 bestPrefix = normalized;
457 if (searchTokensRegex.length() > 0) {
458 searchTokensRegex.append("[\\s]*");
460 searchTokensRegex.append(Pattern.quote(normalized));
462 final Pattern pattern = Pattern.compile(searchTokensRegex.toString());
464 if (bestPrefix == null) {
465 bestPrefix = searchTokens.get(0);
466 System.out.println("Everything was in the stoplist!");
468 System.out.println("Searching using prefix: " + bestPrefix + ", leastRows=" + leastRows
469 + ", searchTokens=" + searchTokens);
471 // Place to store the things that match.
472 final Map<RowMatchType, List<RowBase>> matches = new EnumMap<>(
474 for (final RowMatchType rowMatchType : RowMatchType.values()) {
475 if (rowMatchType != RowMatchType.NO_MATCH) {
476 matches.put(rowMatchType, new ArrayList<RowBase>());
482 final int exactMatchIndex = findInsertionPointIndex(searchText, interrupted);
483 if (exactMatchIndex != -1) {
484 final IndexEntry exactMatch = sortedIndexEntries.get(exactMatchIndex);
485 if (pattern.matcher(exactMatch.token).find()) {
486 matches.get(RowMatchType.TITLE_MATCH).add(rows.get(exactMatch.startRow));
490 final String searchToken = bestPrefix;
491 final int insertionPointIndex = findInsertionPointIndex(searchToken, interrupted);
492 final Set<RowKey> rowsAlreadySeen = new HashSet<>();
493 for (int index = insertionPointIndex; index < sortedIndexEntries.size()
494 && matchCount < MAX_SEARCH_ROWS; ++index) {
495 if (interrupted.get()) {
498 final IndexEntry indexEntry = sortedIndexEntries.get(index);
499 if (!indexEntry.normalizedToken.startsWith(searchToken) &&
500 !NormalizeComparator.withoutDash(indexEntry.normalizedToken).startsWith(searchToken)) {
504 // System.out.println("Searching indexEntry: " + indexEntry.token);
506 // Extra +1 to skip token row.
507 for (int rowIndex = indexEntry.startRow + 1; rowIndex < indexEntry.startRow + 1
509 && rowIndex < rows.size(); ++rowIndex) {
510 if (interrupted.get()) {
513 final RowBase row = rows.get(rowIndex);
514 final RowBase.RowKey rowKey = row.getRowKey();
515 if (rowsAlreadySeen.contains(rowKey)) {
518 rowsAlreadySeen.add(rowKey);
519 final RowMatchType matchType = row.matches(searchTokens, pattern, normalizer(),
521 if (matchType != RowMatchType.NO_MATCH) {
522 matches.get(matchType).add(row);
529 // Sort them into a reasonable order.
530 final RowBase.LengthComparator lengthComparator = new RowBase.LengthComparator(
532 for (final Collection<RowBase> rows : matches.values()) {
533 final List<RowBase> ordered = new ArrayList<>(rows);
534 Collections.sort(ordered, lengthComparator);
535 result.addAll(ordered);
538 System.out.println("searchDuration: " + (System.currentTimeMillis() - startMills));
542 private String normalizeToken(final String searchToken) {
543 if (TransliteratorManager.init(null, null)) {
544 final Transliterator normalizer = normalizer();
545 return normalizer.transliterate(searchToken);
547 // Do our best since the Transliterators aren't up yet.
548 return searchToken.toLowerCase();