~slub.team/goobi-indexserver/3.x

//System.out.println(" label=" + ((char) lastInput.ints[lastInput.offset+idx-1]) + " idx=" + idx + " inputCount=" + frontier[idx].inputCount + " doCompile=" + doCompile + " doPrune=" + doPrune);

215

216

if (node.inputCount < minSuffixCount2 || minSuffixCount2 == 1 && node.inputCount == 1) {

217

// drop all arcs

218

for(int arcIdx=0;arcIdx<node.numArcs;arcIdx++) {

219

@SuppressWarnings("unchecked") final UnCompiledNode<T> target = (UnCompiledNode<T>) node.arcs[arcIdx].target;

220

target.clear();

221

}

222

node.numArcs = 0;

223

}

224

225

if (doPrune) {

226

// this node doesn't make it -- deref it

227

node.clear();

228

parent.deleteLast(lastInput.ints[lastInput.offset+idx-1], node);

229

} else {

230

231

if (minSuffixCount2 != 0) {

232

compileAllTargets(node, lastInput.length-idx);

233

}

234

final T nextFinalOutput = node.output;

235

236

// We "fake" the node as being final if it has no

237

// outgoing arcs; in theory we could leave it

238

// as non-final (the FST can represent this), but

239

// FSTEnum, Util, etc., have trouble w/ non-final

240

// dead-end states:

241

final boolean isFinal = node.isFinal || node.numArcs == 0;

242

243

if (doCompile) {

244

// this node makes it and we now compile it. first,

245

// compile any targets that were previously

246

// undecided:

247

parent.replaceLast(lastInput.ints[lastInput.offset + idx-1],

248

compileNode(node, 1+lastInput.length-idx),

249

nextFinalOutput,

250

isFinal);

251

} else {

252

// replaceLast just to install

253

// nextFinalOutput/isFinal onto the arc

254

parent.replaceLast(lastInput.ints[lastInput.offset + idx-1],

255

node,

256

nextFinalOutput,

257

isFinal);

258

// this node will stay in play for now, since we are

259

// undecided on whether to prune it. later, it

260

// will be either compiled or pruned, so we must

261

// allocate a new node:

262

frontier[idx] = new UnCompiledNode<T>(this, idx);

263

}

264

}

265

}

266

}

267

268

private final IntsRef scratchIntsRef = new IntsRef(10);

269

270

public void add(BytesRef input, T output) throws IOException {

271

assert fst.getInputType() == FST.INPUT_TYPE.BYTE1;

272

scratchIntsRef.grow(input.length);

273

for(int i=0;i<input.length;i++) {

274

scratchIntsRef.ints[i] = input.bytes[i+input.offset] & 0xFF;

275

}

276

scratchIntsRef.length = input.length;

277

add(scratchIntsRef, output);

278

}

279

280

/** Sugar: adds the UTF32 codepoints from char[] slice. FST

281

* must be FST.INPUT_TYPE.BYTE4! */

282

public void add(char[] s, int offset, int length, T output) throws IOException {

283

assert fst.getInputType() == FST.INPUT_TYPE.BYTE4;

284

int charIdx = offset;

285

int intIdx = 0;

286

final int charLimit = offset + length;

287

while(charIdx < charLimit) {

288

scratchIntsRef.grow(intIdx+1);

289

final int utf32 = Character.codePointAt(s, charIdx);

290

scratchIntsRef.ints[intIdx] = utf32;

291

charIdx += Character.charCount(utf32);

292

intIdx++;

293

}

294

scratchIntsRef.length = intIdx;

295

add(scratchIntsRef, output);

296

}

297

298

/** Sugar: adds the UTF32 codepoints from CharSequence. FST

299

* must be FST.INPUT_TYPE.BYTE4! */

300

public void add(CharSequence s, T output) throws IOException {

301

assert fst.getInputType() == FST.INPUT_TYPE.BYTE4;

302

int charIdx = 0;

303

int intIdx = 0;

304

final int charLimit = s.length();

305

while(charIdx < charLimit) {

306

scratchIntsRef.grow(intIdx+1);

307

final int utf32 = Character.codePointAt(s, charIdx);

308

scratchIntsRef.ints[intIdx] = utf32;

309

charIdx += Character.charCount(utf32);

310

intIdx++;

311

}

312

scratchIntsRef.length = intIdx;

313

add(scratchIntsRef, output);

314

}

315

316

/** It's OK to add the same input twice in a row with

317

* different outputs, as long as outputs impls the merge

318

* method. */

319

public void add(IntsRef input, T output) throws IOException {

320

//System.out.println("\nFST ADD: input=" + input + " output=" + fst.outputs.outputToString(output));

321

assert lastInput.length == 0 || input.compareTo(lastInput) >= 0: "inputs are added out of order lastInput=" + lastInput + " vs input=" + input;

322

assert validOutput(output);

323

324

//System.out.println("\nadd: " + input);

325

if (input.length == 0) {

326

// empty input: only allowed as first input. we have

327

// to special case this because the packed FST

328

// format cannot represent the empty input since

329

// 'finalness' is stored on the incoming arc, not on

330

// the node

331

frontier[0].inputCount++;

332

frontier[0].isFinal = true;

333

fst.setEmptyOutput(output);

334

return;

335

}

336

337

// compare shared prefix length

338

int pos1 = 0;

339

int pos2 = input.offset;

340

final int pos1Stop = Math.min(lastInput.length, input.length);

341

while(true) {

342

//System.out.println(" incr " + pos1);

343

frontier[pos1].inputCount++;

344

if (pos1 >= pos1Stop || lastInput.ints[pos1] != input.ints[pos2]) {

345

break;

346

}

347

pos1++;

348

pos2++;

349

}

350

final int prefixLenPlus1 = pos1+1;

351

352

if (frontier.length < input.length+1) {

353

@SuppressWarnings("unchecked") final UnCompiledNode<T>[] next =

354

new UnCompiledNode[ArrayUtil.oversize(input.length+1, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];

355

System.arraycopy(frontier, 0, next, 0, frontier.length);

356

for(int idx=frontier.length;idx<next.length;idx++) {

357

next[idx] = new UnCompiledNode<T>(this, idx);

358

}

359

frontier = next;

360

}

361

362

// minimize/compile states from previous input's

363

// orphan'd suffix

364

compilePrevTail(prefixLenPlus1);

365

366

// init tail states for current input

367

for(int idx=prefixLenPlus1;idx<=input.length;idx++) {

368

frontier[idx-1].addArc(input.ints[input.offset + idx - 1],

369

frontier[idx]);

370

//System.out.println(" incr tail " + idx);

371

frontier[idx].inputCount++;

372

}

373

374

final UnCompiledNode<T> lastNode = frontier[input.length];

375

lastNode.isFinal = true;

376

lastNode.output = NO_OUTPUT;

377

378

// push conflicting outputs forward, only as far as

379

// needed

380

for(int idx=1;idx<prefixLenPlus1;idx++) {

381

final UnCompiledNode<T> node = frontier[idx];

382

final UnCompiledNode<T> parentNode = frontier[idx-1];

383

384

final T lastOutput = parentNode.getLastOutput(input.ints[input.offset + idx - 1]);

385

assert validOutput(lastOutput);

386

387

final T commonOutputPrefix;

388

final T wordSuffix;

389

390

if (lastOutput != NO_OUTPUT) {

391

commonOutputPrefix = fst.outputs.common(output, lastOutput);

392

assert validOutput(commonOutputPrefix);

393

wordSuffix = fst.outputs.subtract(lastOutput, commonOutputPrefix);

394

assert validOutput(wordSuffix);

395

parentNode.setLastOutput(input.ints[input.offset + idx - 1], commonOutputPrefix);

396

node.prependOutput(wordSuffix);

397

} else {

398

commonOutputPrefix = wordSuffix = NO_OUTPUT;

399

}

400

401

output = fst.outputs.subtract(output, commonOutputPrefix);

402

assert validOutput(output);

403

}

404

405

if (lastInput.length == input.length && prefixLenPlus1 == 1+input.length) {

406

// same input more than 1 time in a row, mapping to

407

// multiple outputs

408

lastNode.output = fst.outputs.merge(lastNode.output, output);

409

} else {

410

// this new arc is private to this new input; set its

411

// arc output to the leftover output:

412

frontier[prefixLenPlus1-1].setLastOutput(input.ints[input.offset + prefixLenPlus1-1], output);

413

}

414

415

// save last input

416

lastInput.copy(input);

417

418

//System.out.println(" count[0]=" + frontier[0].inputCount);

419

}

420

421

private boolean validOutput(T output) {

422

return output == NO_OUTPUT || !output.equals(NO_OUTPUT);

423

}

424

425

/** Returns final FST. NOTE: this will return null if

426

* nothing is accepted by the FST. */

427

public FST<T> finish() throws IOException {

428

429

// minimize nodes in the last word's suffix

430

compilePrevTail(1);

431

//System.out.println("finish: inputCount=" + frontier[0].inputCount);

432

if (frontier[0].inputCount < minSuffixCount1 || frontier[0].inputCount < minSuffixCount2 || frontier[0].numArcs == 0) {

433

if (fst.emptyOutput == null) {

434

return null;

435

} else if (minSuffixCount1 > 0 || minSuffixCount2 > 0) {

436

// empty string got pruned

437

return null;

438

} else {

439

fst.finish(compileNode(frontier[0], lastInput.length).address);

440

//System.out.println("compile addr = " + fst.getStartNode());

441

return fst;

442

}

443

} else {

444

if (minSuffixCount2 != 0) {

445

compileAllTargets(frontier[0], lastInput.length);

446

}

447

//System.out.println("NOW: " + frontier[0].numArcs);

448

fst.finish(compileNode(frontier[0], lastInput.length).address);

449

}

450

451

452

if (dedupHash != null) {

453

System.out.println("NH: " + dedupHash.count());

454

}

455

456

457

return fst;

458

}

459

460

private void compileAllTargets(UnCompiledNode<T> node, int tailLength) throws IOException {

461

for(int arcIdx=0;arcIdx<node.numArcs;arcIdx++) {

462

final Arc<T> arc = node.arcs[arcIdx];

463

if (!arc.target.isCompiled()) {

464

// not yet compiled

465

@SuppressWarnings("unchecked") final UnCompiledNode<T> n = (UnCompiledNode<T>) arc.target;

466

if (n.numArcs == 0) {

467

//System.out.println("seg=" + segment + " FORCE final arc=" + (char) arc.label);

468

arc.isFinal = n.isFinal = true;

469

}

470

arc.target = compileNode(n, tailLength-1);

471

}

472

}

473

}

474

475

static class Arc<T> {

476

public int label; // really an "unsigned" byte

477

public Node target;

478

public boolean isFinal;

479

public T output;

480

public T nextFinalOutput;

481

}

482

483

// NOTE: not many instances of Node or CompiledNode are in

484

// memory while the FST is being built; it's only the

485

// current "frontier":

486

487

static interface Node {

488

boolean isCompiled();

489

}

490

491

static final class CompiledNode implements Node {

492

int address;

493

public boolean isCompiled() {

494

return true;

495

}

496

}

497

498

static final class UnCompiledNode<T> implements Node {

499

final Builder<T> owner;

500

int numArcs;

501

Arc<T>[] arcs;

502

T output;

503

boolean isFinal;

504

long inputCount;

505

506

/** This node's depth, starting from the automaton root. */

507

final int depth;

508

509

/**

510

* @param depth

511

* The node's depth starting from the automaton root. Needed for

512

* LUCENE-2934 (node expansion based on conditions other than the

513

* fanout size).

514

515

@SuppressWarnings("unchecked")

516

public UnCompiledNode(Builder<T> owner, int depth) {

517

this.owner = owner;

518

arcs = (Arc<T>[]) new Arc[1];

519

arcs[0] = new Arc<T>();

520

output = owner.NO_OUTPUT;

521

this.depth = depth;

522

}

523

524

public boolean isCompiled() {

525

return false;

526

}

527

528

public void clear() {

529

numArcs = 0;

530

isFinal = false;

531

output = owner.NO_OUTPUT;

532

inputCount = 0;

533

534

// We don't clear the depth here because it never changes

535

// for nodes on the frontier (even when reused).

536

}

537

538

public T getLastOutput(int labelToMatch) {

539

assert numArcs > 0;

540

assert arcs[numArcs-1].label == labelToMatch;

541

return arcs[numArcs-1].output;

542

}

543

544

public void addArc(int label, Node target) {

545

assert label >= 0;

546

assert numArcs == 0 || label > arcs[numArcs-1].label: "arc[-1].label=" + arcs[numArcs-1].label + " new label=" + label + " numArcs=" + numArcs;

547

if (numArcs == arcs.length) {

548

@SuppressWarnings("unchecked") final Arc<T>[] newArcs =

549

new Arc[ArrayUtil.oversize(numArcs+1, RamUsageEstimator.NUM_BYTES_OBJECT_REF)];

550

System.arraycopy(arcs, 0, newArcs, 0, arcs.length);

551

for(int arcIdx=numArcs;arcIdx<newArcs.length;arcIdx++) {

552

newArcs[arcIdx] = new Arc<T>();

553

}

554

arcs = newArcs;

555

}

556

final Arc<T> arc = arcs[numArcs++];

557

arc.label = label;

558

arc.target = target;

559

arc.output = arc.nextFinalOutput = owner.NO_OUTPUT;

560

arc.isFinal = false;

561

}

562

563

public void replaceLast(int labelToMatch, Node target, T nextFinalOutput, boolean isFinal) {

564

assert numArcs > 0;

565

final Arc<T> arc = arcs[numArcs-1];

566

assert arc.label == labelToMatch: "arc.label=" + arc.label + " vs " + labelToMatch;

567

arc.target = target;

568

//assert target.address != -2;

569

arc.nextFinalOutput = nextFinalOutput;

570

arc.isFinal = isFinal;

571

}

572

573

public void deleteLast(int label, Node target) {

574

assert numArcs > 0;

575

assert label == arcs[numArcs-1].label;

576

assert target == arcs[numArcs-1].target;

577

numArcs--;

578

}

579

580

public void setLastOutput(int labelToMatch, T newOutput) {

581

assert owner.validOutput(newOutput);

582

assert numArcs > 0;

583

final Arc<T> arc = arcs[numArcs-1];

584

assert arc.label == labelToMatch;

585

arc.output = newOutput;

586

}

587

588

// pushes an output prefix forward onto all arcs

589

public void prependOutput(T outputPrefix) {

590

assert owner.validOutput(outputPrefix);

591

592

for(int arcIdx=0;arcIdx<numArcs;arcIdx++) {

593

arcs[arcIdx].output = owner.fst.outputs.add(outputPrefix, arcs[arcIdx].output);

594

assert owner.validOutput(arcs[arcIdx].output);

595

}

596

597

if (isFinal) {

598

output = owner.fst.outputs.add(outputPrefix, output);

599

assert owner.validOutput(output);

600

}

601

}

602

}

603

}

Older »