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.TransformingList;
26 import com.hughes.util.raf.RAFList;
27 import com.hughes.util.raf.RAFSerializable;
28 import com.hughes.util.raf.RAFSerializer;
29 import com.hughes.util.raf.SerializableSerializer;
30 import com.hughes.util.raf.UniformRAFList;
31 import com.ibm.icu.text.Collator;
32 import com.ibm.icu.text.Transliterator;
34 import java.io.IOException;
35 import java.io.PrintStream;
36 import java.io.RandomAccessFile;
37 import java.util.ArrayList;
38 import java.util.Collection;
39 import java.util.Collections;
40 import java.util.EnumMap;
41 import java.util.HashSet;
42 import java.util.LinkedHashMap;
43 import java.util.LinkedHashSet;
44 import java.util.List;
47 import java.util.concurrent.atomic.AtomicBoolean;
48 import java.util.regex.Pattern;
50 public final class Index implements RAFSerializable<Index> {
52 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 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 int mainTokenCount = -1;
81 // --------------------------------------------------------------------------
83 public Index(final Dictionary dict, final String shortName, final String longName,
84 final Language sortLanguage, final String normalizerRules,
85 final boolean swapPairEntries, final Set<String> stoplist) {
87 this.shortName = shortName;
88 this.longName = longName;
89 this.sortLanguage = sortLanguage;
90 this.normalizerRules = normalizerRules;
91 this.swapPairEntries = swapPairEntries;
92 sortedIndexEntries = new ArrayList<IndexEntry>();
93 this.stoplist = stoplist;
94 rows = new ArrayList<RowBase>();
100 * Deferred initialization because it can be slow.
102 public synchronized Transliterator normalizer() {
103 if (normalizer == null) {
104 normalizer = Transliterator
105 .createFromRules("", normalizerRules, Transliterator.FORWARD);
111 * Note that using this comparator probably involves doing too many text
114 public NormalizeComparator getSortComparator() {
115 return new NormalizeComparator(normalizer(), sortLanguage.getCollator());
118 public Index(final Dictionary dict, final RandomAccessFile raf) throws IOException {
120 shortName = raf.readUTF();
121 longName = raf.readUTF();
122 final String languageCode = raf.readUTF();
123 sortLanguage = Language.lookup(languageCode);
124 normalizerRules = raf.readUTF();
125 swapPairEntries = raf.readBoolean();
126 if (sortLanguage == null) {
127 throw new IOException("Unsupported language: " + languageCode);
129 if (dict.dictFileVersion >= 2) {
130 mainTokenCount = raf.readInt();
132 sortedIndexEntries = CachingList.create(
133 RAFList.create(raf, indexEntrySerializer, raf.getFilePointer()), CACHE_SIZE);
134 if (dict.dictFileVersion >= 4) {
135 stoplist = new SerializableSerializer<Set<String>>().read(raf);
137 stoplist = Collections.emptySet();
139 rows = CachingList.create(
140 UniformRAFList.create(raf, new RowBase.Serializer(this), raf.getFilePointer()),
145 public void write(final RandomAccessFile raf) throws IOException {
146 raf.writeUTF(shortName);
147 raf.writeUTF(longName);
148 raf.writeUTF(sortLanguage.getIsoCode());
149 raf.writeUTF(normalizerRules);
150 raf.writeBoolean(swapPairEntries);
151 if (dict.dictFileVersion >= 2) {
152 raf.writeInt(mainTokenCount);
154 RAFList.write(raf, sortedIndexEntries, indexEntrySerializer);
155 new SerializableSerializer<Set<String>>().write(raf, stoplist);
156 UniformRAFList.write(raf, (Collection<RowBase>) rows, new RowBase.Serializer(this), 5 /*
163 public void print(final PrintStream out) {
164 for (final RowBase row : rows) {
169 private final RAFSerializer<IndexEntry> indexEntrySerializer = new RAFSerializer<IndexEntry>() {
171 public IndexEntry read(RandomAccessFile raf) throws IOException {
172 return new IndexEntry(Index.this, raf);
176 public void write(RandomAccessFile raf, IndexEntry t) throws IOException {
181 public static final class IndexEntry implements RAFSerializable<Index.IndexEntry> {
182 private final Index index;
183 public final String token;
184 private final String normalizedToken;
185 public final int startRow;
186 public final int numRows; // doesn't count the token row!
187 public final List<HtmlEntry> htmlEntries;
189 public IndexEntry(final Index index, final String token, final String normalizedToken,
190 final int startRow, final int numRows) {
192 assert token.equals(token.trim());
193 assert token.length() > 0;
195 this.normalizedToken = normalizedToken;
196 this.startRow = startRow;
197 this.numRows = numRows;
198 this.htmlEntries = new ArrayList<HtmlEntry>();
201 public IndexEntry(final Index index, final RandomAccessFile raf) throws IOException {
203 token = raf.readUTF();
204 startRow = raf.readInt();
205 numRows = raf.readInt();
206 final boolean hasNormalizedForm = raf.readBoolean();
207 normalizedToken = hasNormalizedForm ? raf.readUTF() : token;
208 if (index.dict.dictFileVersion >= 6) {
209 this.htmlEntries = CachingList.create(
210 RAFList.create(raf, index.dict.htmlEntryIndexSerializer,
211 raf.getFilePointer()), 1);
213 this.htmlEntries = Collections.emptyList();
217 public void write(RandomAccessFile raf) throws IOException {
219 raf.writeInt(startRow);
220 raf.writeInt(numRows);
221 final boolean hasNormalizedForm = !token.equals(normalizedToken);
222 raf.writeBoolean(hasNormalizedForm);
223 if (hasNormalizedForm) {
224 raf.writeUTF(normalizedToken);
226 RAFList.write(raf, htmlEntries, index.dict.htmlEntryIndexSerializer);
229 public String toString() {
230 return String.format("%s@%d(%d)", token, startRow, numRows);
233 public String normalizedToken() {
234 return normalizedToken;
238 static final TransformingList.Transformer<IndexEntry, String> INDEX_ENTRY_TO_TOKEN = new TransformingList.Transformer<IndexEntry, String>() {
240 public String transform(IndexEntry t1) {
245 public IndexEntry findExact(final String exactToken) {
246 final int result = Collections.binarySearch(
247 TransformingList.create(sortedIndexEntries, INDEX_ENTRY_TO_TOKEN), exactToken,
248 getSortComparator());
250 return sortedIndexEntries.get(result);
255 public IndexEntry findInsertionPoint(String token, final AtomicBoolean interrupted) {
256 final int index = findInsertionPointIndex(token, interrupted);
257 return index != -1 ? sortedIndexEntries.get(index) : null;
260 public int findInsertionPointIndex(String token, final AtomicBoolean interrupted) {
261 token = normalizeToken(token);
264 int end = sortedIndexEntries.size();
266 final Collator sortCollator = sortLanguage.getCollator();
267 while (start < end) {
268 final int mid = (start + end) / 2;
269 if (interrupted.get()) {
272 final IndexEntry midEntry = sortedIndexEntries.get(mid);
274 final int comp = sortCollator.compare(token, midEntry.normalizedToken());
276 final int result = windBackCase(token, mid, interrupted);
278 } else if (comp < 0) {
279 // System.out.println("Upper bound: " + midEntry + ", norm=" +
280 // midEntry.normalizedToken() + ", mid=" + mid);
283 // System.out.println("Lower bound: " + midEntry + ", norm=" +
284 // midEntry.normalizedToken() + ", mid=" + mid);
289 // If we search for a substring of a string that's in there, return
291 int result = Math.min(start, sortedIndexEntries.size() - 1);
292 result = windBackCase(sortedIndexEntries.get(result).normalizedToken(), result, interrupted);
296 private final int windBackCase(final String token, int result, final AtomicBoolean interrupted) {
297 while (result > 0 && sortedIndexEntries.get(result - 1).normalizedToken().equals(token)) {
299 if (interrupted.get()) {
306 public IndexInfo getIndexInfo() {
307 return new DictionaryInfo.IndexInfo(shortName, sortedIndexEntries.size(), mainTokenCount);
310 private static final int MAX_SEARCH_ROWS = 1000;
312 private final Map<String, Integer> prefixToNumRows = new LinkedHashMap<String, Integer>();
314 private synchronized final int getUpperBoundOnRowsStartingWith(final String normalizedPrefix,
315 final int maxRows, final AtomicBoolean interrupted) {
316 final Integer numRows = prefixToNumRows.get(normalizedPrefix);
317 if (numRows != null) {
320 final int insertionPointIndex = findInsertionPointIndex(normalizedPrefix, interrupted);
323 for (int index = insertionPointIndex; index < sortedIndexEntries.size(); ++index) {
324 if (interrupted.get()) {
327 final IndexEntry indexEntry = sortedIndexEntries.get(index);
328 if (!indexEntry.normalizedToken.startsWith(normalizedPrefix)) {
331 rowCount += indexEntry.numRows + indexEntry.htmlEntries.size();
332 if (rowCount > maxRows) {
333 System.out.println("Giving up, too many words with prefix: " + normalizedPrefix);
337 prefixToNumRows.put(normalizedPrefix, numRows);
341 public final List<RowBase> multiWordSearch(
342 final String searchText, final List<String> searchTokens,
343 final AtomicBoolean interrupted) {
344 final long startMills = System.currentTimeMillis();
345 final List<RowBase> result = new ArrayList<RowBase>();
347 final Set<String> normalizedNonStoplist = new LinkedHashSet<String>();
349 String bestPrefix = null;
350 int leastRows = Integer.MAX_VALUE;
351 final StringBuilder searchTokensRegex = new StringBuilder();
352 for (int i = 0; i < searchTokens.size(); ++i) {
353 if (interrupted.get()) {
356 final String searchToken = searchTokens.get(i);
357 final String normalized = normalizeToken(searchTokens.get(i));
358 // Normalize them all.
359 searchTokens.set(i, normalized);
361 if (!stoplist.contains(searchToken)) {
362 if (normalizedNonStoplist.add(normalized)) {
363 final int numRows = getUpperBoundOnRowsStartingWith(normalized,
364 MAX_SEARCH_ROWS, interrupted);
365 if (numRows != -1 && numRows < leastRows) {
367 // We really are done here.
368 return Collections.emptyList();
371 bestPrefix = normalized;
376 if (searchTokensRegex.length() > 0) {
377 searchTokensRegex.append("[\\s]*");
379 searchTokensRegex.append(Pattern.quote(normalized));
381 final Pattern pattern = Pattern.compile(searchTokensRegex.toString());
383 if (bestPrefix == null) {
384 bestPrefix = searchTokens.get(0);
385 System.out.println("Everything was in the stoplist!");
387 System.out.println("Searching using prefix: " + bestPrefix + ", leastRows=" + leastRows
388 + ", searchTokens=" + searchTokens);
390 // Place to store the things that match.
391 final Map<RowMatchType, List<RowBase>> matches = new EnumMap<RowMatchType, List<RowBase>>(
393 for (final RowMatchType rowMatchType : RowMatchType.values()) {
394 if (rowMatchType != RowMatchType.NO_MATCH) {
395 matches.put(rowMatchType, new ArrayList<RowBase>());
401 final int exactMatchIndex = findInsertionPointIndex(searchText, interrupted);
402 if (exactMatchIndex != -1) {
403 final IndexEntry exactMatch = sortedIndexEntries.get(exactMatchIndex);
404 if (pattern.matcher(exactMatch.token).find()) {
405 matches.get(RowMatchType.TITLE_MATCH).add(rows.get(exactMatch.startRow));
409 final String searchToken = bestPrefix;
410 final int insertionPointIndex = findInsertionPointIndex(searchToken, interrupted);
411 final Set<RowKey> rowsAlreadySeen = new HashSet<RowBase.RowKey>();
412 for (int index = insertionPointIndex; index < sortedIndexEntries.size()
413 && matchCount < MAX_SEARCH_ROWS; ++index) {
414 if (interrupted.get()) {
417 final IndexEntry indexEntry = sortedIndexEntries.get(index);
418 if (!indexEntry.normalizedToken.startsWith(searchToken)) {
422 // System.out.println("Searching indexEntry: " + indexEntry.token);
424 // Extra +1 to skip token row.
425 for (int rowIndex = indexEntry.startRow + 1; rowIndex < indexEntry.startRow + 1
427 && rowIndex < rows.size(); ++rowIndex) {
428 if (interrupted.get()) {
431 final RowBase row = rows.get(rowIndex);
432 final RowBase.RowKey rowKey = row.getRowKey();
433 if (rowsAlreadySeen.contains(rowKey)) {
436 rowsAlreadySeen.add(rowKey);
437 final RowMatchType matchType = row.matches(searchTokens, pattern, normalizer(),
439 if (matchType != RowMatchType.NO_MATCH) {
440 matches.get(matchType).add(row);
447 // Sort them into a reasonable order.
448 final RowBase.LengthComparator lengthComparator = new RowBase.LengthComparator(
450 for (final Collection<RowBase> rows : matches.values()) {
451 final List<RowBase> ordered = new ArrayList<RowBase>(rows);
452 Collections.sort(ordered, lengthComparator);
453 result.addAll(ordered);
456 System.out.println("searchDuration: " + (System.currentTimeMillis() - startMills));
460 private String normalizeToken(final String searchToken) {
461 if (TransliteratorManager.init(null)) {
462 final Transliterator normalizer = normalizer();
463 return normalizer.transliterate(searchToken);
465 // Do our best since the Transliterators aren't up yet.
466 return searchToken.toLowerCase();