+++ /dev/null
-package org.apache.lucene.analysis.synonym;
-
-/**
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements. See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-import java.io.IOException;
-
-import org.apache.lucene.analysis.TokenFilter;
-import org.apache.lucene.analysis.TokenStream;
-import org.apache.lucene.analysis.tokenattributes.CharTermAttribute;
-import org.apache.lucene.analysis.tokenattributes.OffsetAttribute;
-import org.apache.lucene.analysis.tokenattributes.PositionIncrementAttribute;
-import org.apache.lucene.analysis.tokenattributes.TypeAttribute;
-import org.apache.lucene.store.ByteArrayDataInput;
-import org.apache.lucene.util.ArrayUtil;
-import org.apache.lucene.util.AttributeSource;
-import org.apache.lucene.util.BytesRef;
-import org.apache.lucene.util.CharsRef;
-import org.apache.lucene.util.RamUsageEstimator;
-import org.apache.lucene.util.UnicodeUtil;
-import org.apache.lucene.util.fst.FST;
-
-/**
- * Matches single or multi word synonyms in a token stream.
- * This token stream cannot properly handle position
- * increments != 1, ie, you should place this filter before
- * filtering out stop words.
- *
- * <p>Note that with the current implementation, parsing is
- * greedy, so whenever multiple parses would apply, the rule
- * starting the earliest and parsing the most tokens wins.
- * For example if you have these rules:
- *
- * <pre>
- * a -> x
- * a b -> y
- * b c d -> z
- * </pre>
- *
- * Then input <code>a b c d e</code> parses to <code>y b c
- * d</code>, ie the 2nd rule "wins" because it started
- * earliest and matched the most input tokens of other rules
- * starting at that point.</p>
- *
- * <p>A future improvement to this filter could allow
- * non-greedy parsing, such that the 3rd rule would win, and
- * also separately allow multiple parses, such that all 3
- * rules would match, perhaps even on a rule by rule
- * basis.</p>
- *
- * <p><b>NOTE</b>: when a match occurs, the output tokens
- * associated with the matching rule are "stacked" on top of
- * the input stream (if the rule had
- * <code>keepOrig=true</code>) and also on top of aother
- * matched rule's output tokens. This is not a correct
- * solution, as really the output should be an abitrary
- * graph/lattice. For example, with the above match, you
- * would expect an exact <code>PhraseQuery</code> <code>"y b
- * c"</code> to match the parsed tokens, but it will fail to
- * do so. This limitations is necessary because Lucene's
- * TokenStream (and index) cannot yet represent an arbitrary
- * graph.</p>
- *
- * <p><b>NOTE</b>: If multiple incoming tokens arrive on the
- * same position, only the first token at that position is
- * used for parsing. Subsequent tokens simply pass through
- * and are not parsed. A future improvement would be to
- * allow these tokens to also be matched.</p>
- */
-
-// TODO: maybe we should resolve token -> wordID then run
-// FST on wordIDs, for better perf?
-
-// TODO: a more efficient approach would be Aho/Corasick's
-// algorithm
-// http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm
-// It improves over the current approach here
-// because it does not fully re-start matching at every
-// token. For exampl,e if one pattern is "a b c x"
-// and another is "b c d" and the input is "a b c d", on
-// trying to parse "a b c x" but failing when you got to x,
-// rather than starting over again your really should
-// immediately recognize that "b c d" matches at the next
-// input. I suspect this won't matter that much in
-// practice, but it's possible on some set of synonyms it
-// will. We'd have to modify Aho/Corasick to enforce our
-// conflict resolving (eg greedy matching) because that algo
-// finds all matches.
-
-public final class SynonymFilter extends TokenFilter {
-
- public static final String TYPE_SYNONYM = "SYNONYM";
-
- private final SynonymMap synonyms;
-
- private final boolean ignoreCase;
- private final int rollBufferSize;
-
- private int captureCount;
-
- private final CharTermAttribute termAtt = addAttribute(CharTermAttribute.class);
- private final PositionIncrementAttribute posIncrAtt = addAttribute(PositionIncrementAttribute.class);
- private final TypeAttribute typeAtt = addAttribute(TypeAttribute.class);
- private final OffsetAttribute offsetAtt = addAttribute(OffsetAttribute.class);
-
- // How many future input tokens have already been matched
- // to a synonym; because the matching is "greedy" we don't
- // try to do any more matching for such tokens:
- private int inputSkipCount;
-
- // Hold all buffered (read ahead) stacked input tokens for
- // a future position. When multiple tokens are at the
- // same position, we only store (and match against) the
- // term for the first token at the position, but capture
- // state for (and enumerate) all other tokens at this
- // position:
- private static class PendingInput {
- final CharsRef term = new CharsRef();
- AttributeSource.State state;
- boolean keepOrig;
- boolean matched;
- boolean consumed = true;
- int startOffset;
- int endOffset;
-
- public void reset() {
- state = null;
- consumed = true;
- keepOrig = false;
- matched = false;
- }
- };
-
- // Rolling buffer, holding pending input tokens we had to
- // clone because we needed to look ahead, indexed by
- // position:
- private final PendingInput[] futureInputs;
-
- // Holds pending output synonyms for one future position:
- private static class PendingOutputs {
- CharsRef[] outputs;
- int upto;
- int count;
- int posIncr = 1;
-
- public PendingOutputs() {
- outputs = new CharsRef[1];
- }
-
- public void reset() {
- upto = count = 0;
- posIncr = 1;
- }
-
- public CharsRef pullNext() {
- assert upto < count;
- final CharsRef result = outputs[upto++];
- posIncr = 0;
- if (upto == count) {
- reset();
- }
- return result;
- }
-
- public void add(char[] output, int offset, int len) {
- if (count == outputs.length) {
- final CharsRef[] next = new CharsRef[ArrayUtil.oversize(1+count, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];
- System.arraycopy(outputs, 0, next, 0, count);
- outputs = next;
- }
- if (outputs[count] == null) {
- outputs[count] = new CharsRef();
- }
- outputs[count].copy(output, offset, len);
- count++;
- }
- };
-
- private final ByteArrayDataInput bytesReader = new ByteArrayDataInput();
-
- // Rolling buffer, holding stack of pending synonym
- // outputs, indexed by position:
- private final PendingOutputs[] futureOutputs;
-
- // Where (in rolling buffers) to write next input saved state:
- private int nextWrite;
-
- // Where (in rolling buffers) to read next input saved state:
- private int nextRead;
-
- // True once we've read last token
- private boolean finished;
-
- private final FST.Arc<BytesRef> scratchArc;
-
- private final FST<BytesRef> fst;
-
- private final BytesRef scratchBytes = new BytesRef();
- private final CharsRef scratchChars = new CharsRef();
-
- /**
- * @param input input tokenstream
- * @param synonyms synonym map
- * @param ignoreCase case-folds input for matching with {@link Character#toLowerCase(int)}.
- * Note, if you set this to true, its your responsibility to lowercase
- * the input entries when you create the {@link SynonymMap}
- */
- public SynonymFilter(TokenStream input, SynonymMap synonyms, boolean ignoreCase) {
- super(input);
- this.synonyms = synonyms;
- this.ignoreCase = ignoreCase;
- this.fst = synonyms.fst;
-
- if (fst == null) {
- throw new IllegalArgumentException("fst must be non-null");
- }
-
- // Must be 1+ so that when roll buffer is at full
- // lookahead we can distinguish this full buffer from
- // the empty buffer:
- rollBufferSize = 1+synonyms.maxHorizontalContext;
-
- futureInputs = new PendingInput[rollBufferSize];
- futureOutputs = new PendingOutputs[rollBufferSize];
- for(int pos=0;pos<rollBufferSize;pos++) {
- futureInputs[pos] = new PendingInput();
- futureOutputs[pos] = new PendingOutputs();
- }
-
- //System.out.println("FSTFilt maxH=" + synonyms.maxHorizontalContext);
-
- scratchArc = new FST.Arc<BytesRef>();
- }
-
- private void capture() {
- captureCount++;
- //System.out.println(" capture slot=" + nextWrite);
- final PendingInput input = futureInputs[nextWrite];
-
- input.state = captureState();
- input.consumed = false;
- input.term.copy(termAtt.buffer(), 0, termAtt.length());
-
- nextWrite = rollIncr(nextWrite);
-
- // Buffer head should never catch up to tail:
- assert nextWrite != nextRead;
- }
-
- /*
- This is the core of this TokenFilter: it locates the
- synonym matches and buffers up the results into
- futureInputs/Outputs.
-
- NOTE: this calls input.incrementToken and does not
- capture the state if no further tokens were checked. So
- caller must then forward state to our caller, or capture:
- */
-
- private void parse() throws IOException {
- //System.out.println("\nS: parse");
-
- assert inputSkipCount == 0;
-
- int curNextRead = nextRead;
-
- // Holds the longest match we've seen so far:
- BytesRef matchOutput = null;
- int matchInputLength = 0;
-
- BytesRef pendingOutput = fst.outputs.getNoOutput();
- fst.getFirstArc(scratchArc);
-
- assert scratchArc.output == fst.outputs.getNoOutput();
-
- int tokenCount = 0;
-
- byToken:
- while(true) {
-
- // Pull next token's chars:
- final char[] buffer;
- final int bufferLen;
- //System.out.println(" cycle nextRead=" + curNextRead + " nextWrite=" + nextWrite);
-
- if (curNextRead == nextWrite) {
-
- // We used up our lookahead buffer of input tokens
- // -- pull next real input token:
-
- if (finished) {
- break;
- } else {
- //System.out.println(" input.incrToken");
- assert futureInputs[nextWrite].consumed;
- // Not correct: a syn match whose output is longer
- // than its input can set future inputs keepOrig
- // to true:
- //assert !futureInputs[nextWrite].keepOrig;
- if (input.incrementToken()) {
- buffer = termAtt.buffer();
- bufferLen = termAtt.length();
- final PendingInput input = futureInputs[nextWrite];
- input.startOffset = offsetAtt.startOffset();
- input.endOffset = offsetAtt.endOffset();
- //System.out.println(" new token=" + new String(buffer, 0, bufferLen));
- if (nextRead != nextWrite) {
- capture();
- } else {
- input.consumed = false;
- }
-
- } else {
- // No more input tokens
- //System.out.println(" set end");
- finished = true;
- break;
- }
- }
- } else {
- // Still in our lookahead
- buffer = futureInputs[curNextRead].term.chars;
- bufferLen = futureInputs[curNextRead].term.length;
- //System.out.println(" old token=" + new String(buffer, 0, bufferLen));
- }
-
- tokenCount++;
-
- // Run each char in this token through the FST:
- int bufUpto = 0;
- while(bufUpto < bufferLen) {
- final int codePoint = Character.codePointAt(buffer, bufUpto, bufferLen);
- if (fst.findTargetArc(ignoreCase ? Character.toLowerCase(codePoint) : codePoint, scratchArc, scratchArc) == null) {
- //System.out.println(" stop");
- break byToken;
- }
-
- // Accum the output
- pendingOutput = fst.outputs.add(pendingOutput, scratchArc.output);
- //System.out.println(" char=" + buffer[bufUpto] + " output=" + pendingOutput + " arc.output=" + scratchArc.output);
- bufUpto += Character.charCount(codePoint);
- }
-
- // OK, entire token matched; now see if this is a final
- // state:
- if (scratchArc.isFinal()) {
- matchOutput = fst.outputs.add(pendingOutput, scratchArc.nextFinalOutput);
- matchInputLength = tokenCount;
- //System.out.println(" found matchLength=" + matchInputLength + " output=" + matchOutput);
- }
-
- // See if the FST wants to continue matching (ie, needs to
- // see the next input token):
- if (fst.findTargetArc(SynonymMap.WORD_SEPARATOR, scratchArc, scratchArc) == null) {
- // No further rules can match here; we're done
- // searching for matching rules starting at the
- // current input position.
- break;
- } else {
- // More matching is possible -- accum the output (if
- // any) of the WORD_SEP arc:
- pendingOutput = fst.outputs.add(pendingOutput, scratchArc.output);
- if (nextRead == nextWrite) {
- capture();
- }
- }
-
- curNextRead = rollIncr(curNextRead);
- }
-
- if (nextRead == nextWrite && !finished) {
- //System.out.println(" skip write slot=" + nextWrite);
- nextWrite = rollIncr(nextWrite);
- }
-
- if (matchOutput != null) {
- //System.out.println(" add matchLength=" + matchInputLength + " output=" + matchOutput);
- inputSkipCount = matchInputLength;
- addOutput(matchOutput, matchInputLength);
- } else if (nextRead != nextWrite) {
- // Even though we had no match here, we set to 1
- // because we need to skip current input token before
- // trying to match again:
- inputSkipCount = 1;
- } else {
- assert finished;
- }
-
- //System.out.println(" parse done inputSkipCount=" + inputSkipCount + " nextRead=" + nextRead + " nextWrite=" + nextWrite);
- }
-
- // Interleaves all output tokens onto the futureOutputs:
- private void addOutput(BytesRef bytes, int matchInputLength) {
- bytesReader.reset(bytes.bytes, bytes.offset, bytes.length);
-
- final int code = bytesReader.readVInt();
- final boolean keepOrig = (code & 0x1) == 0;
- final int count = code >>> 1;
- //System.out.println(" addOutput count=" + count + " keepOrig=" + keepOrig);
- for(int outputIDX=0;outputIDX<count;outputIDX++) {
- synonyms.words.get(bytesReader.readVInt(),
- scratchBytes);
- //System.out.println(" outIDX=" + outputIDX + " bytes=" + scratchBytes.length);
- UnicodeUtil.UTF8toUTF16(scratchBytes, scratchChars);
- int lastStart = scratchChars.offset;
- final int chEnd = lastStart + scratchChars.length;
- int outputUpto = nextRead;
- for(int chIDX=lastStart;chIDX<=chEnd;chIDX++) {
- if (chIDX == chEnd || scratchChars.chars[chIDX] == SynonymMap.WORD_SEPARATOR) {
- final int outputLen = chIDX - lastStart;
- // Caller is not allowed to have empty string in
- // the output:
- assert outputLen > 0: "output contains empty string: " + scratchChars;
- futureOutputs[outputUpto].add(scratchChars.chars, lastStart, outputLen);
- //System.out.println(" " + new String(scratchChars.chars, lastStart, outputLen) + " outputUpto=" + outputUpto);
- lastStart = 1+chIDX;
- //System.out.println(" slot=" + outputUpto + " keepOrig=" + keepOrig);
- outputUpto = rollIncr(outputUpto);
- assert futureOutputs[outputUpto].posIncr == 1: "outputUpto=" + outputUpto + " vs nextWrite=" + nextWrite;
- }
- }
- }
-
- int upto = nextRead;
- for(int idx=0;idx<matchInputLength;idx++) {
- futureInputs[upto].keepOrig |= keepOrig;
- futureInputs[upto].matched = true;
- upto = rollIncr(upto);
- }
- }
-
- // ++ mod rollBufferSize
- private int rollIncr(int count) {
- count++;
- if (count == rollBufferSize) {
- return 0;
- } else {
- return count;
- }
- }
-
- // for testing
- int getCaptureCount() {
- return captureCount;
- }
-
- @Override
- public boolean incrementToken() throws IOException {
-
- //System.out.println("\nS: incrToken inputSkipCount=" + inputSkipCount + " nextRead=" + nextRead + " nextWrite=" + nextWrite);
-
- while(true) {
-
- // First play back any buffered future inputs/outputs
- // w/o running parsing again:
- while (inputSkipCount != 0) {
-
- // At each position, we first output the original
- // token
-
- // TODO: maybe just a PendingState class, holding
- // both input & outputs?
- final PendingInput input = futureInputs[nextRead];
- final PendingOutputs outputs = futureOutputs[nextRead];
-
- //System.out.println(" cycle nextRead=" + nextRead + " nextWrite=" + nextWrite + " inputSkipCount="+ inputSkipCount + " input.keepOrig=" + input.keepOrig + " input.consumed=" + input.consumed + " input.state=" + input.state);
-
- if (!input.consumed && (input.keepOrig || !input.matched)) {
- if (input.state != null) {
- // Return a previously saved token (because we
- // had to lookahead):
- restoreState(input.state);
- } else {
- // Pass-through case: return token we just pulled
- // but didn't capture:
- assert inputSkipCount == 1: "inputSkipCount=" + inputSkipCount + " nextRead=" + nextRead;
- }
- input.reset();
- if (outputs.count > 0) {
- outputs.posIncr = 0;
- } else {
- nextRead = rollIncr(nextRead);
- inputSkipCount--;
- }
- //System.out.println(" return token=" + termAtt.toString());
- return true;
- } else if (outputs.upto < outputs.count) {
- // Still have pending outputs to replay at this
- // position
- input.reset();
- final int posIncr = outputs.posIncr;
- final CharsRef output = outputs.pullNext();
- clearAttributes();
- termAtt.copyBuffer(output.chars, output.offset, output.length);
- typeAtt.setType(TYPE_SYNONYM);
- offsetAtt.setOffset(input.startOffset, input.endOffset);
- posIncrAtt.setPositionIncrement(posIncr);
- if (outputs.count == 0) {
- // Done with the buffered input and all outputs at
- // this position
- nextRead = rollIncr(nextRead);
- inputSkipCount--;
- }
- //System.out.println(" return token=" + termAtt.toString());
- return true;
- } else {
- // Done with the buffered input and all outputs at
- // this position
- input.reset();
- nextRead = rollIncr(nextRead);
- inputSkipCount--;
- }
- }
-
- if (finished && nextRead == nextWrite) {
- // End case: if any output syns went beyond end of
- // input stream, enumerate them now:
- final PendingOutputs outputs = futureOutputs[nextRead];
- if (outputs.upto < outputs.count) {
- final int posIncr = outputs.posIncr;
- final CharsRef output = outputs.pullNext();
- futureInputs[nextRead].reset();
- if (outputs.count == 0) {
- nextWrite = nextRead = rollIncr(nextRead);
- }
- clearAttributes();
- termAtt.copyBuffer(output.chars, output.offset, output.length);
- typeAtt.setType(TYPE_SYNONYM);
- //System.out.println(" set posIncr=" + outputs.posIncr + " outputs=" + outputs);
- posIncrAtt.setPositionIncrement(posIncr);
- //System.out.println(" return token=" + termAtt.toString());
- return true;
- } else {
- return false;
- }
- }
-
- // Find new synonym matches:
- parse();
- }
- }
-
- @Override
- public void reset() throws IOException {
- super.reset();
- captureCount = 0;
- finished = false;
-
- // In normal usage these resets would not be needed,
- // since they reset-as-they-are-consumed, but the app
- // may not consume all input tokens in which case we
- // have leftover state here:
- for (PendingInput input : futureInputs) {
- input.reset();
- }
- for (PendingOutputs output : futureOutputs) {
- output.reset();
- }
- }
-}
fnp / pylucene.git / blobdiff