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.
19 package com.hughes.android.dictionary.engine;
21 import com.hughes.android.dictionary.DictionaryInfo;
22 import com.hughes.android.dictionary.DictionaryInfo.IndexInfo;
23 import com.hughes.android.dictionary.engine.RowBase.RowKey;
24 import com.hughes.util.CachingList;
25 import com.hughes.util.StringUtil;
26 import com.hughes.util.TransformingList;
27 import com.hughes.util.raf.RAFList;
28 import com.hughes.util.raf.RAFSerializable;
29 import com.hughes.util.raf.RAFSerializer;
30 import com.hughes.util.raf.SerializableSerializer;
31 import com.hughes.util.raf.UniformRAFList;
32 import com.ibm.icu.text.Transliterator;
34 import java.io.DataInput;
35 import java.io.DataInputStream;
36 import java.io.DataOutput;
37 import java.io.IOException;
38 import java.io.PrintStream;
39 import java.io.RandomAccessFile;
40 import java.nio.channels.Channels;
41 import java.nio.channels.FileChannel;
42 import java.util.AbstractList;
43 import java.util.ArrayList;
44 import java.util.Collection;
45 import java.util.Collections;
46 import java.util.Comparator;
47 import java.util.EnumMap;
48 import java.util.HashSet;
49 import java.util.HashMap;
50 import java.util.List;
53 import java.util.concurrent.atomic.AtomicBoolean;
54 import java.util.regex.Pattern;
56 public final class Index implements RAFSerializable<Index> {
58 static final int CACHE_SIZE = 5000;
60 public final Dictionary dict;
62 public final String shortName; // Typically the ISO code for the language.
63 public final String longName;
65 // persisted: tells how the entries are sorted.
66 public final Language sortLanguage;
67 final String normalizerRules;
69 // Built from the two above.
70 private Transliterator normalizer;
73 public final List<IndexEntry> sortedIndexEntries;
76 public final Set<String> stoplist;
81 public final List<RowBase> rows;
82 public final boolean swapPairEntries;
85 int mainTokenCount = -1;
87 // --------------------------------------------------------------------------
89 public Index(final Dictionary dict, final String shortName, final String longName,
90 final Language sortLanguage, final String normalizerRules,
91 final boolean swapPairEntries, final Set<String> stoplist) {
93 this.shortName = shortName;
94 this.longName = longName;
95 this.sortLanguage = sortLanguage;
96 this.normalizerRules = normalizerRules;
97 this.swapPairEntries = swapPairEntries;
98 sortedIndexEntries = new ArrayList<IndexEntry>();
99 this.stoplist = stoplist;
100 rows = new ArrayList<RowBase>();
106 * Deferred initialization because it can be slow.
108 public synchronized Transliterator normalizer() {
109 if (normalizer == null) {
110 normalizer = TransliteratorManager.get(normalizerRules);
116 * Note that using this comparator probably involves doing too many text
119 public NormalizeComparator getSortComparator() {
120 return new NormalizeComparator(normalizer(), sortLanguage.getCollator(), dict.dictFileVersion);
123 public Index(final Dictionary dict, final FileChannel inp, final DataInput raf) throws IOException {
125 shortName = raf.readUTF();
126 longName = raf.readUTF();
127 final String languageCode = raf.readUTF();
128 sortLanguage = Language.lookup(languageCode);
129 normalizerRules = raf.readUTF();
130 swapPairEntries = raf.readBoolean();
131 if (sortLanguage == null) {
132 throw new IOException("Unsupported language: " + languageCode);
134 if (dict.dictFileVersion >= 2) {
135 mainTokenCount = raf.readInt();
137 sortedIndexEntries = CachingList.create(
138 RAFList.create(inp, new IndexEntrySerializer(dict.dictFileVersion == 6 ? inp : null), inp.position(),
139 dict.dictFileVersion, dict.dictInfo + " idx " + languageCode + ": "), CACHE_SIZE);
140 if (dict.dictFileVersion >= 7) {
141 int count = StringUtil.readVarInt(raf);
142 stoplist = new HashSet<String>(count);
143 for (int i = 0; i < count; ++i) {
144 stoplist.add(raf.readUTF());
146 } else if (dict.dictFileVersion >= 4) {
147 stoplist = new SerializableSerializer<Set<String>>().read(raf);
149 stoplist = Collections.emptySet();
151 rows = CachingList.create(
152 UniformRAFList.create(inp, new RowBase.Serializer(this), inp.position()),
157 public void write(final DataOutput out) throws IOException {
158 RandomAccessFile raf = (RandomAccessFile)out;
159 raf.writeUTF(shortName);
160 raf.writeUTF(longName);
161 raf.writeUTF(sortLanguage.getIsoCode());
162 raf.writeUTF(normalizerRules);
163 raf.writeBoolean(swapPairEntries);
164 if (dict.dictFileVersion >= 2) {
165 raf.writeInt(mainTokenCount);
167 RAFList.write(raf, sortedIndexEntries, new IndexEntrySerializer(null), 32, true);
168 StringUtil.writeVarInt(raf, stoplist.size());
169 for (String i : stoplist) {
172 UniformRAFList.write(raf, rows, new RowBase.Serializer(this), 3 /* bytes per entry */);
175 public void print(final PrintStream out) {
176 for (final RowBase row : rows) {
181 private final class IndexEntrySerializer implements RAFSerializer<IndexEntry> {
182 private final FileChannel ch;
184 public IndexEntrySerializer(FileChannel ch) {
189 public IndexEntry read(DataInput raf) throws IOException {
190 return new IndexEntry(Index.this, ch, raf);
194 public void write(DataOutput raf, IndexEntry t) throws IOException {
199 public static final class IndexEntry implements RAFSerializable<Index.IndexEntry> {
200 public final String token;
201 private final String normalizedToken;
202 public final int startRow;
203 public final int numRows; // doesn't count the token row!
204 public List<HtmlEntry> htmlEntries;
206 public IndexEntry(final Index index, final String token, final String normalizedToken,
207 final int startRow, final int numRows) {
208 assert token.equals(token.trim());
209 assert token.length() > 0;
211 this.normalizedToken = normalizedToken;
212 this.startRow = startRow;
213 this.numRows = numRows;
214 this.htmlEntries = new ArrayList<HtmlEntry>();
217 public IndexEntry(final Index index, final FileChannel ch, final DataInput raf) throws IOException {
218 token = raf.readUTF();
219 if (index.dict.dictFileVersion >= 7) {
220 startRow = StringUtil.readVarInt(raf);
221 numRows = StringUtil.readVarInt(raf);
223 startRow = raf.readInt();
224 numRows = raf.readInt();
226 final boolean hasNormalizedForm = raf.readBoolean();
227 normalizedToken = hasNormalizedForm ? raf.readUTF() : token;
228 if (index.dict.dictFileVersion >= 7) {
229 int size = StringUtil.readVarInt(raf);
231 this.htmlEntries = Collections.emptyList();
233 final int[] htmlEntryIndices = new int[size];
234 for (int i = 0; i < size; ++i) {
235 htmlEntryIndices[i] = StringUtil.readVarInt(raf);
237 this.htmlEntries = new AbstractList<HtmlEntry>() {
239 public HtmlEntry get(int i) {
240 return index.dict.htmlEntries.get(htmlEntryIndices[i]);
244 return htmlEntryIndices.length;
248 } else if (index.dict.dictFileVersion >= 6) {
249 this.htmlEntries = CachingList.create(
250 RAFList.create(ch, index.dict.htmlEntryIndexSerializer,
251 ch.position(), index.dict.dictFileVersion,
252 index.dict.dictInfo + " htmlEntries: "), 1);
254 this.htmlEntries = Collections.emptyList();
258 public void write(DataOutput raf) throws IOException {
260 StringUtil.writeVarInt(raf, startRow);
261 StringUtil.writeVarInt(raf, numRows);
262 final boolean hasNormalizedForm = !token.equals(normalizedToken);
263 raf.writeBoolean(hasNormalizedForm);
264 if (hasNormalizedForm) {
265 raf.writeUTF(normalizedToken);
267 StringUtil.writeVarInt(raf, htmlEntries.size());
268 for (HtmlEntry e : htmlEntries)
269 StringUtil.writeVarInt(raf, e.index());
272 public String toString() {
273 return String.format("%s@%d(%d)", token, startRow, numRows);
276 public String normalizedToken() {
277 return normalizedToken;
281 static final TransformingList.Transformer<IndexEntry, String> INDEX_ENTRY_TO_TOKEN = new TransformingList.Transformer<IndexEntry, String>() {
283 public String transform(IndexEntry t1) {
288 public IndexEntry findExact(final String exactToken) {
289 final int result = Collections.binarySearch(
290 TransformingList.create(sortedIndexEntries, INDEX_ENTRY_TO_TOKEN), exactToken,
291 getSortComparator());
293 return sortedIndexEntries.get(result);
298 public IndexEntry findInsertionPoint(String token, final AtomicBoolean interrupted) {
299 final int index = findInsertionPointIndex(token, interrupted);
300 return index != -1 ? sortedIndexEntries.get(index) : null;
303 private int compareIdx(String token, final Comparator sortCollator, int idx) {
304 final IndexEntry entry = sortedIndexEntries.get(idx);
305 return NormalizeComparator.compareWithoutDash(token, entry.normalizedToken(), sortCollator, dict.dictFileVersion);
308 public int findInsertionPointIndex(String token, final AtomicBoolean interrupted) {
309 token = normalizeToken(token);
312 int end = sortedIndexEntries.size();
314 final Comparator sortCollator = sortLanguage.getCollator();
315 while (start < end) {
316 final int mid = (start + end) / 2;
317 if (interrupted.get()) {
320 final IndexEntry midEntry = sortedIndexEntries.get(mid);
322 int comp = NormalizeComparator.compareWithoutDash(token, midEntry.normalizedToken(), sortCollator, dict.dictFileVersion);
324 comp = sortCollator.compare(token, midEntry.normalizedToken());
326 final int result = windBackCase(token, mid, interrupted);
328 } else if (comp < 0) {
329 // System.out.println("Upper bound: " + midEntry + ", norm=" +
330 // midEntry.normalizedToken() + ", mid=" + mid);
332 // Hack for robustness if sort order is broken
334 compareIdx(token, sortCollator, mid + 1) > 0 &&
335 compareIdx(token, sortCollator, mid + 2) > 0) {
341 // System.out.println("Lower bound: " + midEntry + ", norm=" +
342 // midEntry.normalizedToken() + ", mid=" + mid);
344 // Hack for robustness if sort order is broken
345 if (mid - 2 >= start &&
346 compareIdx(token, sortCollator, mid - 1) < 0 &&
347 compareIdx(token, sortCollator, mid - 2) < 0) {
355 // If we search for a substring of a string that's in there, return
357 int result = Math.min(start, sortedIndexEntries.size() - 1);
358 result = windBackCase(sortedIndexEntries.get(result).normalizedToken(), result, interrupted);
362 private final int windBackCase(final String token, int result, final AtomicBoolean interrupted) {
363 while (result > 0 && sortedIndexEntries.get(result - 1).normalizedToken().equals(token)) {
365 if (interrupted.get()) {
372 public IndexInfo getIndexInfo() {
373 return new DictionaryInfo.IndexInfo(shortName, sortedIndexEntries.size(), mainTokenCount);
376 private static final int MAX_SEARCH_ROWS = 1000;
378 private final Map<String, Integer> prefixToNumRows = new HashMap<String, Integer>();
380 private synchronized final int getUpperBoundOnRowsStartingWith(final String normalizedPrefix,
381 final int maxRows, final AtomicBoolean interrupted) {
382 final Integer numRows = prefixToNumRows.get(normalizedPrefix);
383 if (numRows != null) {
386 final int insertionPointIndex = findInsertionPointIndex(normalizedPrefix, interrupted);
389 for (int index = insertionPointIndex; index < sortedIndexEntries.size(); ++index) {
390 if (interrupted.get()) {
393 final IndexEntry indexEntry = sortedIndexEntries.get(index);
394 if (!indexEntry.normalizedToken.startsWith(normalizedPrefix)) {
397 rowCount += indexEntry.numRows + indexEntry.htmlEntries.size();
398 if (rowCount > maxRows) {
399 System.out.println("Giving up, too many words with prefix: " + normalizedPrefix);
403 prefixToNumRows.put(normalizedPrefix, numRows);
407 public final List<RowBase> multiWordSearch(
408 final String searchText, final List<String> searchTokens,
409 final AtomicBoolean interrupted) {
410 final long startMills = System.currentTimeMillis();
411 final List<RowBase> result = new ArrayList<RowBase>();
413 final Set<String> normalizedNonStoplist = new HashSet<String>();
415 String bestPrefix = null;
416 int leastRows = Integer.MAX_VALUE;
417 final StringBuilder searchTokensRegex = new StringBuilder();
418 for (int i = 0; i < searchTokens.size(); ++i) {
419 if (interrupted.get()) {
422 final String searchToken = searchTokens.get(i);
423 final String normalized = normalizeToken(searchTokens.get(i));
424 // Normalize them all.
425 searchTokens.set(i, normalized);
427 if (!stoplist.contains(searchToken)) {
428 if (normalizedNonStoplist.add(normalized)) {
429 final int numRows = getUpperBoundOnRowsStartingWith(normalized,
430 MAX_SEARCH_ROWS, interrupted);
431 if (numRows != -1 && numRows < leastRows) {
433 // We really are done here.
434 return Collections.emptyList();
437 bestPrefix = normalized;
442 if (searchTokensRegex.length() > 0) {
443 searchTokensRegex.append("[\\s]*");
445 searchTokensRegex.append(Pattern.quote(normalized));
447 final Pattern pattern = Pattern.compile(searchTokensRegex.toString());
449 if (bestPrefix == null) {
450 bestPrefix = searchTokens.get(0);
451 System.out.println("Everything was in the stoplist!");
453 System.out.println("Searching using prefix: " + bestPrefix + ", leastRows=" + leastRows
454 + ", searchTokens=" + searchTokens);
456 // Place to store the things that match.
457 final Map<RowMatchType, List<RowBase>> matches = new EnumMap<RowMatchType, List<RowBase>>(
459 for (final RowMatchType rowMatchType : RowMatchType.values()) {
460 if (rowMatchType != RowMatchType.NO_MATCH) {
461 matches.put(rowMatchType, new ArrayList<RowBase>());
467 final int exactMatchIndex = findInsertionPointIndex(searchText, interrupted);
468 if (exactMatchIndex != -1) {
469 final IndexEntry exactMatch = sortedIndexEntries.get(exactMatchIndex);
470 if (pattern.matcher(exactMatch.token).find()) {
471 matches.get(RowMatchType.TITLE_MATCH).add(rows.get(exactMatch.startRow));
475 final String searchToken = bestPrefix;
476 final int insertionPointIndex = findInsertionPointIndex(searchToken, interrupted);
477 final Set<RowKey> rowsAlreadySeen = new HashSet<RowBase.RowKey>();
478 for (int index = insertionPointIndex; index < sortedIndexEntries.size()
479 && matchCount < MAX_SEARCH_ROWS; ++index) {
480 if (interrupted.get()) {
483 final IndexEntry indexEntry = sortedIndexEntries.get(index);
484 if (!indexEntry.normalizedToken.startsWith(searchToken)) {
488 // System.out.println("Searching indexEntry: " + indexEntry.token);
490 // Extra +1 to skip token row.
491 for (int rowIndex = indexEntry.startRow + 1; rowIndex < indexEntry.startRow + 1
493 && rowIndex < rows.size(); ++rowIndex) {
494 if (interrupted.get()) {
497 final RowBase row = rows.get(rowIndex);
498 final RowBase.RowKey rowKey = row.getRowKey();
499 if (rowsAlreadySeen.contains(rowKey)) {
502 rowsAlreadySeen.add(rowKey);
503 final RowMatchType matchType = row.matches(searchTokens, pattern, normalizer(),
505 if (matchType != RowMatchType.NO_MATCH) {
506 matches.get(matchType).add(row);
513 // Sort them into a reasonable order.
514 final RowBase.LengthComparator lengthComparator = new RowBase.LengthComparator(
516 for (final Collection<RowBase> rows : matches.values()) {
517 final List<RowBase> ordered = new ArrayList<RowBase>(rows);
518 Collections.sort(ordered, lengthComparator);
519 result.addAll(ordered);
522 System.out.println("searchDuration: " + (System.currentTimeMillis() - startMills));
526 private String normalizeToken(final String searchToken) {
527 if (TransliteratorManager.init(null, null)) {
528 final Transliterator normalizer = normalizer();
529 return normalizer.transliterate(searchToken);
531 // Do our best since the Transliterators aren't up yet.
532 return searchToken.toLowerCase();