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