src/com/hughes/android/dictionary/engine/Index.java

   1 // Copyright 2011 Google Inc. All Rights Reserved.
   2 //
   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
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   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.
  14
  15 /**
  16  *
  17  */
  18
  19 package com.hughes.android.dictionary.engine;
  20
  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 java.text.Collator;
  33 import com.ibm.icu.text.Transliterator;
  34
  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;
  50 import java.util.Map;
  51 import java.util.Set;
  52 import java.util.concurrent.atomic.AtomicBoolean;
  53 import java.util.regex.Pattern;
  54
  55 public final class Index implements RAFSerializable<Index> {
  56
  57     static final int CACHE_SIZE = 5000;
  58
  59     public final Dictionary dict;
  60
  61     public final String shortName; // Typically the ISO code for the language.
  62     public final String longName;
  63
  64     // persisted: tells how the entries are sorted.
  65     public final Language sortLanguage;
  66     final String normalizerRules;
  67
  68     // Built from the two above.
  69     private Transliterator normalizer;
  70
  71     // persisted
  72     public final List<IndexEntry> sortedIndexEntries;
  73
  74     // persisted.
  75     public final Set<String> stoplist;
  76
  77     // One big list!
  78     // Various sub-types.
  79     // persisted
  80     public final List<RowBase> rows;
  81     public final boolean swapPairEntries;
  82
  83     // Version 2:
  84     int mainTokenCount = -1;
  85
  86     // --------------------------------------------------------------------------
  87
  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) {
  91         this.dict = dict;
  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>();
 100
 101         normalizer = null;
 102     }
 103
 104     /**
 105      * Deferred initialization because it can be slow.
 106      */
 107     public synchronized Transliterator normalizer() {
 108         if (normalizer == null) {
 109             normalizer = Transliterator
 110                     .createFromRules("", normalizerRules, Transliterator.FORWARD);
 111         }
 112         return normalizer;
 113     }
 114
 115     /**
 116      * Note that using this comparator probably involves doing too many text
 117      * normalizations.
 118      */
 119     public NormalizeComparator getSortComparator() {
 120         return new NormalizeComparator(normalizer(), sortLanguage.getCollator(), dict.dictFileVersion);
 121     }
 122
 123     public Index(final Dictionary dict, final DataInput inp) throws IOException {
 124         this.dict = dict;
 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);
 134         }
 135         if (dict.dictFileVersion >= 2) {
 136             mainTokenCount = raf.readInt();
 137         }
 138         sortedIndexEntries = CachingList.create(
 139                 RAFList.create(raf, indexEntrySerializer, raf.getFilePointer(),
 140                                dict.dictFileVersion, dict.dictInfo + " idx " + languageCode + ": "), CACHE_SIZE);
 141         if (dict.dictFileVersion >= 7) {
 142             int count = StringUtil.readVarInt(raf);
 143             stoplist = new HashSet<String>(count);
 144             for (int i = 0; i < count; ++i) {
 145                 stoplist.add(raf.readUTF());
 146             }
 147         } else if (dict.dictFileVersion >= 4) {
 148             stoplist = new SerializableSerializer<Set<String>>().read(raf);
 149         } else {
 150             stoplist = Collections.emptySet();
 151         }
 152         rows = CachingList.create(
 153                 UniformRAFList.create(raf, new RowBase.Serializer(this), raf.getFilePointer()),
 154                 CACHE_SIZE);
 155     }
 156
 157     @Override
 158     public void write(final DataOutput out) throws IOException {
 159         RandomAccessFile raf = (RandomAccessFile)out;
 160         raf.writeUTF(shortName);
 161         raf.writeUTF(longName);
 162         raf.writeUTF(sortLanguage.getIsoCode());
 163         raf.writeUTF(normalizerRules);
 164         raf.writeBoolean(swapPairEntries);
 165         if (dict.dictFileVersion >= 2) {
 166             raf.writeInt(mainTokenCount);
 167         }
 168         RAFList.write(raf, sortedIndexEntries, indexEntrySerializer, 32, true);
 169         StringUtil.writeVarInt(raf, stoplist.size());
 170         for (String i : stoplist) {
 171             raf.writeUTF(i);
 172         }
 173         UniformRAFList.write(raf, rows, new RowBase.Serializer(this), 3 /* bytes per entry */);
 174     }
 175
 176     public void print(final PrintStream out) {
 177         for (final RowBase row : rows) {
 178             row.print(out);
 179         }
 180     }
 181
 182     private final RAFSerializer<IndexEntry> indexEntrySerializer = new RAFSerializer<IndexEntry>() {
 183         @Override
 184         public IndexEntry read(DataInput raf) throws IOException {
 185             return new IndexEntry(Index.this, raf);
 186         }
 187
 188         @Override
 189         public void write(DataOutput raf, IndexEntry t) throws IOException {
 190             t.write(raf);
 191         }
 192     };
 193
 194     public static final class IndexEntry implements RAFSerializable<Index.IndexEntry> {
 195         private final Index index;
 196         public final String token;
 197         private final String normalizedToken;
 198         public final int startRow;
 199         public final int numRows; // doesn't count the token row!
 200         public List<HtmlEntry> htmlEntries;
 201         private int[] htmlEntryIndices;
 202
 203         public IndexEntry(final Index index, final String token, final String normalizedToken,
 204                 final int startRow, final int numRows) {
 205             this.index = index;
 206             assert token.equals(token.trim());
 207             assert token.length() > 0;
 208             this.token = token;
 209             this.normalizedToken = normalizedToken;
 210             this.startRow = startRow;
 211             this.numRows = numRows;
 212             this.htmlEntries = new ArrayList<HtmlEntry>();
 213         }
 214
 215         public IndexEntry(final Index index, final DataInput raf) throws IOException {
 216             this.index = index;
 217             token = raf.readUTF();
 218             if (index.dict.dictFileVersion >= 7) {
 219                 startRow = StringUtil.readVarInt(raf);
 220                 numRows = StringUtil.readVarInt(raf);
 221             } else {
 222                 startRow = raf.readInt();
 223                 numRows = raf.readInt();
 224             }
 225             final boolean hasNormalizedForm = raf.readBoolean();
 226             normalizedToken = hasNormalizedForm ? raf.readUTF() : token;
 227             htmlEntryIndices = null;
 228             if (index.dict.dictFileVersion >= 7) {
 229                 int size = StringUtil.readVarInt(raf);
 230                 htmlEntryIndices = new int[size];
 231                 for (int i = 0; i < size; ++i) {
 232                     htmlEntryIndices[i] = StringUtil.readVarInt(raf);
 233                 }
 234                 this.htmlEntries = CachingList.create(new AbstractList<HtmlEntry>() {
 235                     @Override
 236                     public HtmlEntry get(int i) {
 237                         return index.dict.htmlEntries.get(htmlEntryIndices[i]);
 238                     }
 239                     @Override
 240                     public int size() {
 241                         return htmlEntryIndices.length;
 242                     }
 243                     }, 1);
 244             } else if (index.dict.dictFileVersion >= 6) {
 245                 this.htmlEntries = CachingList.create(
 246                         RAFList.create((RandomAccessFile)raf, index.dict.htmlEntryIndexSerializer,
 247                                 ((RandomAccessFile)raf).getFilePointer(), index.dict.dictFileVersion,
 248                                 index.dict.dictInfo + " htmlEntries: "), 1);
 249             } else {
 250                 this.htmlEntries = Collections.emptyList();
 251             }
 252         }
 253
 254         public void write(DataOutput raf) throws IOException {
 255             raf.writeUTF(token);
 256             StringUtil.writeVarInt(raf, startRow);
 257             StringUtil.writeVarInt(raf, numRows);
 258             final boolean hasNormalizedForm = !token.equals(normalizedToken);
 259             raf.writeBoolean(hasNormalizedForm);
 260             if (hasNormalizedForm) {
 261                 raf.writeUTF(normalizedToken);
 262             }
 263             StringUtil.writeVarInt(raf, htmlEntries.size());
 264             for (HtmlEntry e : htmlEntries)
 265                 StringUtil.writeVarInt(raf, e.index());
 266         }
 267
 268         public String toString() {
 269             return String.format("%s@%d(%d)", token, startRow, numRows);
 270         }
 271
 272         public String normalizedToken() {
 273             return normalizedToken;
 274         }
 275     }
 276
 277     static final TransformingList.Transformer<IndexEntry, String> INDEX_ENTRY_TO_TOKEN = new TransformingList.Transformer<IndexEntry, String>() {
 278         @Override
 279         public String transform(IndexEntry t1) {
 280             return t1.token;
 281         }
 282     };
 283
 284     public IndexEntry findExact(final String exactToken) {
 285         final int result = Collections.binarySearch(
 286                 TransformingList.create(sortedIndexEntries, INDEX_ENTRY_TO_TOKEN), exactToken,
 287                 getSortComparator());
 288         if (result >= 0) {
 289             return sortedIndexEntries.get(result);
 290         }
 291         return null;
 292     }
 293
 294     public IndexEntry findInsertionPoint(String token, final AtomicBoolean interrupted) {
 295         final int index = findInsertionPointIndex(token, interrupted);
 296         return index != -1 ? sortedIndexEntries.get(index) : null;
 297     }
 298
 299     public int findInsertionPointIndex(String token, final AtomicBoolean interrupted) {
 300         token = normalizeToken(token);
 301
 302         int start = 0;
 303         int end = sortedIndexEntries.size();
 304
 305         final Comparator sortCollator = sortLanguage.getCollator();
 306         while (start < end) {
 307             final int mid = (start + end) / 2;
 308             if (interrupted.get()) {
 309                 return -1;
 310             }
 311             final IndexEntry midEntry = sortedIndexEntries.get(mid);
 312
 313             int comp = NormalizeComparator.compareWithoutLeadingDash(token, midEntry.normalizedToken(), sortCollator, dict.dictFileVersion);
 314             if (comp == 0)
 315                 comp = sortCollator.compare(token, midEntry.normalizedToken());
 316             if (comp == 0) {
 317                 final int result = windBackCase(token, mid, interrupted);
 318                 return result;
 319             } else if (comp < 0) {
 320                 // System.out.println("Upper bound: " + midEntry + ", norm=" +
 321                 // midEntry.normalizedToken() + ", mid=" + mid);
 322                 end = mid;
 323             } else {
 324                 // System.out.println("Lower bound: " + midEntry + ", norm=" +
 325                 // midEntry.normalizedToken() + ", mid=" + mid);
 326                 start = mid + 1;
 327             }
 328         }
 329
 330         // If we search for a substring of a string that's in there, return
 331         // that.
 332         int result = Math.min(start, sortedIndexEntries.size() - 1);
 333         result = windBackCase(sortedIndexEntries.get(result).normalizedToken(), result, interrupted);
 334         return result;
 335     }
 336
 337     private final int windBackCase(final String token, int result, final AtomicBoolean interrupted) {
 338         while (result > 0 && sortedIndexEntries.get(result - 1).normalizedToken().equals(token)) {
 339             --result;
 340             if (interrupted.get()) {
 341                 return result;
 342             }
 343         }
 344         return result;
 345     }
 346
 347     public IndexInfo getIndexInfo() {
 348         return new DictionaryInfo.IndexInfo(shortName, sortedIndexEntries.size(), mainTokenCount);
 349     }
 350
 351     private static final int MAX_SEARCH_ROWS = 1000;
 352
 353     private final Map<String, Integer> prefixToNumRows = new LinkedHashMap<String, Integer>();
 354
 355     private synchronized final int getUpperBoundOnRowsStartingWith(final String normalizedPrefix,
 356             final int maxRows, final AtomicBoolean interrupted) {
 357         final Integer numRows = prefixToNumRows.get(normalizedPrefix);
 358         if (numRows != null) {
 359             return numRows;
 360         }
 361         final int insertionPointIndex = findInsertionPointIndex(normalizedPrefix, interrupted);
 362
 363         int rowCount = 0;
 364         for (int index = insertionPointIndex; index < sortedIndexEntries.size(); ++index) {
 365             if (interrupted.get()) {
 366                 return -1;
 367             }
 368             final IndexEntry indexEntry = sortedIndexEntries.get(index);
 369             if (!indexEntry.normalizedToken.startsWith(normalizedPrefix)) {
 370                 break;
 371             }
 372             rowCount += indexEntry.numRows + indexEntry.htmlEntries.size();
 373             if (rowCount > maxRows) {
 374                 System.out.println("Giving up, too many words with prefix: " + normalizedPrefix);
 375                 break;
 376             }
 377         }
 378         prefixToNumRows.put(normalizedPrefix, numRows);
 379         return rowCount;
 380     }
 381
 382     public final List<RowBase> multiWordSearch(
 383             final String searchText, final List<String> searchTokens,
 384             final AtomicBoolean interrupted) {
 385         final long startMills = System.currentTimeMillis();
 386         final List<RowBase> result = new ArrayList<RowBase>();
 387
 388         final Set<String> normalizedNonStoplist = new LinkedHashSet<String>();
 389
 390         String bestPrefix = null;
 391         int leastRows = Integer.MAX_VALUE;
 392         final StringBuilder searchTokensRegex = new StringBuilder();
 393         for (int i = 0; i < searchTokens.size(); ++i) {
 394             if (interrupted.get()) {
 395                 return null;
 396             }
 397             final String searchToken = searchTokens.get(i);
 398             final String normalized = normalizeToken(searchTokens.get(i));
 399             // Normalize them all.
 400             searchTokens.set(i, normalized);
 401
 402             if (!stoplist.contains(searchToken)) {
 403                 if (normalizedNonStoplist.add(normalized)) {
 404                     final int numRows = getUpperBoundOnRowsStartingWith(normalized,
 405                             MAX_SEARCH_ROWS, interrupted);
 406                     if (numRows != -1 && numRows < leastRows) {
 407                         if (numRows == 0) {
 408                             // We really are done here.
 409                             return Collections.emptyList();
 410                         }
 411                         leastRows = numRows;
 412                         bestPrefix = normalized;
 413                     }
 414                 }
 415             }
 416
 417             if (searchTokensRegex.length() > 0) {
 418                 searchTokensRegex.append("[\\s]*");
 419             }
 420             searchTokensRegex.append(Pattern.quote(normalized));
 421         }
 422         final Pattern pattern = Pattern.compile(searchTokensRegex.toString());
 423
 424         if (bestPrefix == null) {
 425             bestPrefix = searchTokens.get(0);
 426             System.out.println("Everything was in the stoplist!");
 427         }
 428         System.out.println("Searching using prefix: " + bestPrefix + ", leastRows=" + leastRows
 429                 + ", searchTokens=" + searchTokens);
 430
 431         // Place to store the things that match.
 432         final Map<RowMatchType, List<RowBase>> matches = new EnumMap<RowMatchType, List<RowBase>>(
 433                 RowMatchType.class);
 434         for (final RowMatchType rowMatchType : RowMatchType.values()) {
 435             if (rowMatchType != RowMatchType.NO_MATCH) {
 436                 matches.put(rowMatchType, new ArrayList<RowBase>());
 437             }
 438         }
 439
 440         int matchCount = 0;
 441
 442         final int exactMatchIndex = findInsertionPointIndex(searchText, interrupted);
 443         if (exactMatchIndex != -1) {
 444             final IndexEntry exactMatch = sortedIndexEntries.get(exactMatchIndex);
 445             if (pattern.matcher(exactMatch.token).find()) {
 446                 matches.get(RowMatchType.TITLE_MATCH).add(rows.get(exactMatch.startRow));
 447             }
 448         }
 449
 450         final String searchToken = bestPrefix;
 451         final int insertionPointIndex = findInsertionPointIndex(searchToken, interrupted);
 452         final Set<RowKey> rowsAlreadySeen = new HashSet<RowBase.RowKey>();
 453         for (int index = insertionPointIndex; index < sortedIndexEntries.size()
 454                 && matchCount < MAX_SEARCH_ROWS; ++index) {
 455             if (interrupted.get()) {
 456                 return null;
 457             }
 458             final IndexEntry indexEntry = sortedIndexEntries.get(index);
 459             if (!indexEntry.normalizedToken.startsWith(searchToken)) {
 460                 break;
 461             }
 462
 463             // System.out.println("Searching indexEntry: " + indexEntry.token);
 464
 465             // Extra +1 to skip token row.
 466             for (int rowIndex = indexEntry.startRow + 1; rowIndex < indexEntry.startRow + 1
 467                     + indexEntry.numRows
 468                     && rowIndex < rows.size(); ++rowIndex) {
 469                 if (interrupted.get()) {
 470                     return null;
 471                 }
 472                 final RowBase row = rows.get(rowIndex);
 473                 final RowBase.RowKey rowKey = row.getRowKey();
 474                 if (rowsAlreadySeen.contains(rowKey)) {
 475                     continue;
 476                 }
 477                 rowsAlreadySeen.add(rowKey);
 478                 final RowMatchType matchType = row.matches(searchTokens, pattern, normalizer(),
 479                         swapPairEntries);
 480                 if (matchType != RowMatchType.NO_MATCH) {
 481                     matches.get(matchType).add(row);
 482                     ++matchCount;
 483                 }
 484             }
 485         }
 486         // } // searchTokens
 487
 488         // Sort them into a reasonable order.
 489         final RowBase.LengthComparator lengthComparator = new RowBase.LengthComparator(
 490                 swapPairEntries);
 491         for (final Collection<RowBase> rows : matches.values()) {
 492             final List<RowBase> ordered = new ArrayList<RowBase>(rows);
 493             Collections.sort(ordered, lengthComparator);
 494             result.addAll(ordered);
 495         }
 496
 497         System.out.println("searchDuration: " + (System.currentTimeMillis() - startMills));
 498         return result;
 499     }
 500
 501     private String normalizeToken(final String searchToken) {
 502         if (TransliteratorManager.init(null)) {
 503             final Transliterator normalizer = normalizer();
 504             return normalizer.transliterate(searchToken);
 505         } else {
 506             // Do our best since the Transliterators aren't up yet.
 507             return searchToken.toLowerCase();
 508         }
 509     }
 510
 511 }