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