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.Collator;
33 import com.ibm.icu.text.Transliterator;
35 import java.io.DataInput;
36 import java.io.DataOutput;
37 import java.io.IOException;
38 import java.io.PrintStream;
39 import java.io.RandomAccessFile;
40 import java.util.AbstractList;
41 import java.util.ArrayList;
42 import java.util.Collection;
43 import java.util.Collections;
44 import java.util.Comparator;
45 import java.util.EnumMap;
46 import java.util.HashSet;
47 import java.util.LinkedHashMap;
48 import java.util.LinkedHashSet;
49 import java.util.List;
52 import java.util.concurrent.atomic.AtomicBoolean;
53 import java.util.regex.Pattern;
55 public final class Index implements RAFSerializable<Index> {
57 static final int CACHE_SIZE = 5000;
59 public final Dictionary dict;
61 public final String shortName; // Typically the ISO code for the language.
62 public final String longName;
64 // persisted: tells how the entries are sorted.
65 public final Language sortLanguage;
66 final String normalizerRules;
68 // Built from the two above.
69 private Transliterator normalizer;
72 public final List<IndexEntry> sortedIndexEntries;
75 public final Set<String> stoplist;
80 public final List<RowBase> rows;
81 public final boolean swapPairEntries;
84 int mainTokenCount = -1;
86 // --------------------------------------------------------------------------
88 public Index(final Dictionary dict, final String shortName, final String longName,
89 final Language sortLanguage, final String normalizerRules,
90 final boolean swapPairEntries, final Set<String> stoplist) {
92 this.shortName = shortName;
93 this.longName = longName;
94 this.sortLanguage = sortLanguage;
95 this.normalizerRules = normalizerRules;
96 this.swapPairEntries = swapPairEntries;
97 sortedIndexEntries = new ArrayList<IndexEntry>();
98 this.stoplist = stoplist;
99 rows = new ArrayList<RowBase>();
105 * Deferred initialization because it can be slow.
107 public synchronized Transliterator normalizer() {
108 if (normalizer == null) {
109 normalizer = Transliterator
110 .createFromRules("", normalizerRules, Transliterator.FORWARD);
116 * Note that using this comparator probably involves doing too many text
119 public NormalizeComparator getSortComparator() {
120 return new NormalizeComparator(normalizer(), sortLanguage.getCollator());
123 public Index(final Dictionary dict, final DataInput inp) throws IOException {
125 RandomAccessFile raf = (RandomAccessFile)inp;
126 shortName = raf.readUTF();
127 longName = raf.readUTF();
128 final String languageCode = raf.readUTF();
129 sortLanguage = Language.lookup(languageCode);
130 normalizerRules = raf.readUTF();
131 swapPairEntries = raf.readBoolean();
132 if (sortLanguage == null) {
133 throw new IOException("Unsupported language: " + languageCode);
135 if (dict.dictFileVersion >= 2) {
136 mainTokenCount = raf.readInt();
138 sortedIndexEntries = CachingList.create(
139 RAFList.create(raf, indexEntrySerializer, raf.getFilePointer(), dict.dictFileVersion,
140 dict.dictFileVersion >= 7 ? 16 : 1, dict.dictFileVersion >= 7), CACHE_SIZE);
141 if (dict.dictFileVersion >= 4) {
142 stoplist = new SerializableSerializer<Set<String>>().read(raf);
144 stoplist = Collections.emptySet();
146 rows = CachingList.create(
147 UniformRAFList.create(raf, new RowBase.Serializer(this), raf.getFilePointer()),
152 public void write(final DataOutput out) throws IOException {
153 RandomAccessFile raf = (RandomAccessFile)out;
154 raf.writeUTF(shortName);
155 raf.writeUTF(longName);
156 raf.writeUTF(sortLanguage.getIsoCode());
157 raf.writeUTF(normalizerRules);
158 raf.writeBoolean(swapPairEntries);
159 if (dict.dictFileVersion >= 2) {
160 raf.writeInt(mainTokenCount);
162 RAFList.write(raf, sortedIndexEntries, indexEntrySerializer, 16, true);
163 new SerializableSerializer<Set<String>>().write(raf, 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 RAFSerializer<IndexEntry> indexEntrySerializer = new RAFSerializer<IndexEntry>() {
175 public IndexEntry read(DataInput raf) throws IOException {
176 return new IndexEntry(Index.this, raf);
180 public void write(DataOutput raf, IndexEntry t) throws IOException {
185 public static final class IndexEntry implements RAFSerializable<Index.IndexEntry> {
186 private final Index index;
187 public final String token;
188 private final String normalizedToken;
189 public final int startRow;
190 public final int numRows; // doesn't count the token row!
191 public List<HtmlEntry> htmlEntries;
192 private int[] htmlEntryIndices;
194 public IndexEntry(final Index index, final String token, final String normalizedToken,
195 final int startRow, final int numRows) {
197 assert token.equals(token.trim());
198 assert token.length() > 0;
200 this.normalizedToken = normalizedToken;
201 this.startRow = startRow;
202 this.numRows = numRows;
203 this.htmlEntries = new ArrayList<HtmlEntry>();
206 public IndexEntry(final Index index, final DataInput raf) throws IOException {
208 token = raf.readUTF();
209 if (index.dict.dictFileVersion >= 7) {
210 startRow = StringUtil.readVarInt(raf);
211 numRows = StringUtil.readVarInt(raf);
213 startRow = raf.readInt();
214 numRows = raf.readInt();
216 final boolean hasNormalizedForm = raf.readBoolean();
217 normalizedToken = hasNormalizedForm ? raf.readUTF() : token;
218 htmlEntryIndices = null;
219 if (index.dict.dictFileVersion >= 7) {
220 int size = StringUtil.readVarInt(raf);
221 htmlEntryIndices = new int[size];
222 for (int i = 0; i < size; ++i) {
223 htmlEntryIndices[i] = StringUtil.readVarInt(raf);
225 this.htmlEntries = CachingList.create(new AbstractList<HtmlEntry>() {
227 public HtmlEntry get(int i) {
228 return index.dict.htmlEntries.get(htmlEntryIndices[i]);
232 return htmlEntryIndices.length;
235 } else if (index.dict.dictFileVersion >= 6) {
236 this.htmlEntries = CachingList.create(
237 RAFList.create((RandomAccessFile)raf, index.dict.htmlEntryIndexSerializer,
238 ((RandomAccessFile)raf).getFilePointer(), index.dict.dictFileVersion), 1);
240 this.htmlEntries = Collections.emptyList();
244 public void write(DataOutput raf) throws IOException {
246 StringUtil.writeVarInt(raf, startRow);
247 StringUtil.writeVarInt(raf, numRows);
248 final boolean hasNormalizedForm = !token.equals(normalizedToken);
249 raf.writeBoolean(hasNormalizedForm);
250 if (hasNormalizedForm) {
251 raf.writeUTF(normalizedToken);
253 StringUtil.writeVarInt(raf, htmlEntries.size());
254 for (HtmlEntry e : htmlEntries)
255 StringUtil.writeVarInt(raf, e.index());
258 public String toString() {
259 return String.format("%s@%d(%d)", token, startRow, numRows);
262 public String normalizedToken() {
263 return normalizedToken;
267 static final TransformingList.Transformer<IndexEntry, String> INDEX_ENTRY_TO_TOKEN = new TransformingList.Transformer<IndexEntry, String>() {
269 public String transform(IndexEntry t1) {
274 public IndexEntry findExact(final String exactToken) {
275 final int result = Collections.binarySearch(
276 TransformingList.create(sortedIndexEntries, INDEX_ENTRY_TO_TOKEN), exactToken,
277 getSortComparator());
279 return sortedIndexEntries.get(result);
284 public IndexEntry findInsertionPoint(String token, final AtomicBoolean interrupted) {
285 final int index = findInsertionPointIndex(token, interrupted);
286 return index != -1 ? sortedIndexEntries.get(index) : null;
289 public int findInsertionPointIndex(String token, final AtomicBoolean interrupted) {
290 token = normalizeToken(token);
293 int end = sortedIndexEntries.size();
295 final Comparator sortCollator = sortLanguage.getCollator();
296 while (start < end) {
297 final int mid = (start + end) / 2;
298 if (interrupted.get()) {
301 final IndexEntry midEntry = sortedIndexEntries.get(mid);
303 final int comp = sortCollator.compare(token, midEntry.normalizedToken());
305 final int result = windBackCase(token, mid, interrupted);
307 } else if (comp < 0) {
308 // System.out.println("Upper bound: " + midEntry + ", norm=" +
309 // midEntry.normalizedToken() + ", mid=" + mid);
312 // System.out.println("Lower bound: " + midEntry + ", norm=" +
313 // midEntry.normalizedToken() + ", mid=" + mid);
318 // If we search for a substring of a string that's in there, return
320 int result = Math.min(start, sortedIndexEntries.size() - 1);
321 result = windBackCase(sortedIndexEntries.get(result).normalizedToken(), result, interrupted);
325 private final int windBackCase(final String token, int result, final AtomicBoolean interrupted) {
326 while (result > 0 && sortedIndexEntries.get(result - 1).normalizedToken().equals(token)) {
328 if (interrupted.get()) {
335 public IndexInfo getIndexInfo() {
336 return new DictionaryInfo.IndexInfo(shortName, sortedIndexEntries.size(), mainTokenCount);
339 private static final int MAX_SEARCH_ROWS = 1000;
341 private final Map<String, Integer> prefixToNumRows = new LinkedHashMap<String, Integer>();
343 private synchronized final int getUpperBoundOnRowsStartingWith(final String normalizedPrefix,
344 final int maxRows, final AtomicBoolean interrupted) {
345 final Integer numRows = prefixToNumRows.get(normalizedPrefix);
346 if (numRows != null) {
349 final int insertionPointIndex = findInsertionPointIndex(normalizedPrefix, interrupted);
352 for (int index = insertionPointIndex; index < sortedIndexEntries.size(); ++index) {
353 if (interrupted.get()) {
356 final IndexEntry indexEntry = sortedIndexEntries.get(index);
357 if (!indexEntry.normalizedToken.startsWith(normalizedPrefix)) {
360 rowCount += indexEntry.numRows + indexEntry.htmlEntries.size();
361 if (rowCount > maxRows) {
362 System.out.println("Giving up, too many words with prefix: " + normalizedPrefix);
366 prefixToNumRows.put(normalizedPrefix, numRows);
370 public final List<RowBase> multiWordSearch(
371 final String searchText, final List<String> searchTokens,
372 final AtomicBoolean interrupted) {
373 final long startMills = System.currentTimeMillis();
374 final List<RowBase> result = new ArrayList<RowBase>();
376 final Set<String> normalizedNonStoplist = new LinkedHashSet<String>();
378 String bestPrefix = null;
379 int leastRows = Integer.MAX_VALUE;
380 final StringBuilder searchTokensRegex = new StringBuilder();
381 for (int i = 0; i < searchTokens.size(); ++i) {
382 if (interrupted.get()) {
385 final String searchToken = searchTokens.get(i);
386 final String normalized = normalizeToken(searchTokens.get(i));
387 // Normalize them all.
388 searchTokens.set(i, normalized);
390 if (!stoplist.contains(searchToken)) {
391 if (normalizedNonStoplist.add(normalized)) {
392 final int numRows = getUpperBoundOnRowsStartingWith(normalized,
393 MAX_SEARCH_ROWS, interrupted);
394 if (numRows != -1 && numRows < leastRows) {
396 // We really are done here.
397 return Collections.emptyList();
400 bestPrefix = normalized;
405 if (searchTokensRegex.length() > 0) {
406 searchTokensRegex.append("[\\s]*");
408 searchTokensRegex.append(Pattern.quote(normalized));
410 final Pattern pattern = Pattern.compile(searchTokensRegex.toString());
412 if (bestPrefix == null) {
413 bestPrefix = searchTokens.get(0);
414 System.out.println("Everything was in the stoplist!");
416 System.out.println("Searching using prefix: " + bestPrefix + ", leastRows=" + leastRows
417 + ", searchTokens=" + searchTokens);
419 // Place to store the things that match.
420 final Map<RowMatchType, List<RowBase>> matches = new EnumMap<RowMatchType, List<RowBase>>(
422 for (final RowMatchType rowMatchType : RowMatchType.values()) {
423 if (rowMatchType != RowMatchType.NO_MATCH) {
424 matches.put(rowMatchType, new ArrayList<RowBase>());
430 final int exactMatchIndex = findInsertionPointIndex(searchText, interrupted);
431 if (exactMatchIndex != -1) {
432 final IndexEntry exactMatch = sortedIndexEntries.get(exactMatchIndex);
433 if (pattern.matcher(exactMatch.token).find()) {
434 matches.get(RowMatchType.TITLE_MATCH).add(rows.get(exactMatch.startRow));
438 final String searchToken = bestPrefix;
439 final int insertionPointIndex = findInsertionPointIndex(searchToken, interrupted);
440 final Set<RowKey> rowsAlreadySeen = new HashSet<RowBase.RowKey>();
441 for (int index = insertionPointIndex; index < sortedIndexEntries.size()
442 && matchCount < MAX_SEARCH_ROWS; ++index) {
443 if (interrupted.get()) {
446 final IndexEntry indexEntry = sortedIndexEntries.get(index);
447 if (!indexEntry.normalizedToken.startsWith(searchToken)) {
451 // System.out.println("Searching indexEntry: " + indexEntry.token);
453 // Extra +1 to skip token row.
454 for (int rowIndex = indexEntry.startRow + 1; rowIndex < indexEntry.startRow + 1
456 && rowIndex < rows.size(); ++rowIndex) {
457 if (interrupted.get()) {
460 final RowBase row = rows.get(rowIndex);
461 final RowBase.RowKey rowKey = row.getRowKey();
462 if (rowsAlreadySeen.contains(rowKey)) {
465 rowsAlreadySeen.add(rowKey);
466 final RowMatchType matchType = row.matches(searchTokens, pattern, normalizer(),
468 if (matchType != RowMatchType.NO_MATCH) {
469 matches.get(matchType).add(row);
476 // Sort them into a reasonable order.
477 final RowBase.LengthComparator lengthComparator = new RowBase.LengthComparator(
479 for (final Collection<RowBase> rows : matches.values()) {
480 final List<RowBase> ordered = new ArrayList<RowBase>(rows);
481 Collections.sort(ordered, lengthComparator);
482 result.addAll(ordered);
485 System.out.println("searchDuration: " + (System.currentTimeMillis() - startMills));
489 private String normalizeToken(final String searchToken) {
490 if (TransliteratorManager.init(null)) {
491 final Transliterator normalizer = normalizer();
492 return normalizer.transliterate(searchToken);
494 // Do our best since the Transliterators aren't up yet.
495 return searchToken.toLowerCase();