Background
I am since a long time ago developing a JavaFX application for creating and analysing 'Mech loadouts for Mechwarrior Online.
I previously had a very crude search function based on a FilteredList and a big and complicated predicate. This proved to have many drawbacks, prefix hits were a pain to do and this made searching hard as you had to correctly spell long strings which weren't always obvious.
I have replaced the above implementation with an actual search index based on the Inverted Index approach.
As this is production code that depends on the core data structures of my application, I cannot give an easily runnable example. But if you want, you can fetch the source tree from github and run the tests with ./gradlew test and if you want, you can run the application with ./gradlew run, if you're using Windows cmd.exe, then change ./gradlew to gradlew.bat.
One comment on update(): I made a decision to simply rebuild the index if any of the documents got updated, I found it to be very hard to find which entries in the index matched to to the updated document as the old terms were not available any more to compare to (pointed to document had changed).
I store the full keyword (phrase?) because in the future I intend to support "match all words in this order in one attribute" syntax.
Source
Here is the implementation (github):
/*
* @formatter:off
* Li Song Mechlab - A 'mech building tool for PGI's MechWarrior: Online.
* Copyright (C) 2013 Emily Björk
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
//@formatter:on
package org.lisoft.lsml.model.search;
import java.util.*;
import org.lisoft.lsml.model.chassi.Chassis;
import org.lisoft.lsml.model.item.Faction;
import org.lisoft.lsml.model.loadout.Loadout;
import org.lisoft.lsml.model.modifiers.Modifier;
/**
* A search index that can be used for finding loadouts based on keywords
*
* @author Emily Björk
*/
public class SearchIndex {
private final static String ALL_DOCUMENTS = "";
private boolean dirty = false;
private final Map<String, Set<Loadout>> invertedIndex = new HashMap<>();
private void addPrefixes(Loadout aLoadout, String aKeyword) {
if (null == aKeyword) {
// These keywords will never be null in production but makes
// setting up tests much easier.
return;
}
if (aKeyword.contains(" ")) {
for (final String part : aKeyword.split(" ")) {
addPrefixes(aLoadout, part);
}
}
String prefix = aKeyword.toLowerCase();
while (!prefix.isEmpty()) {
final Set<Loadout> documents = documentsByKey(prefix);
documents.add(aLoadout);
prefix = prefix.substring(0, prefix.length() - 1);
}
}
private Set<Loadout> documentsByKey(String aKeyword) {
return invertedIndex.computeIfAbsent(aKeyword, k -> new HashSet<>());
}
/**
* Merges the given loadout into the search index.
*
* @param aLoadout
* A loadout to merge
*/
public void merge(Loadout aLoadout) {
documentsByKey(ALL_DOCUMENTS).add(aLoadout);
addPrefixes(aLoadout, aLoadout.getName());
final Chassis chassis = aLoadout.getChassis();
addPrefixes(aLoadout, chassis.getSeriesName());
addPrefixes(aLoadout, chassis.getShortName());
addPrefixes(aLoadout, chassis.getName());
addPrefixes(aLoadout, Integer.toString(chassis.getMassMax()) + "ton");
addPrefixes(aLoadout, Integer.toString(chassis.getMassMax()) + " ton");
final Faction faction = chassis.getFaction();
addPrefixes(aLoadout, faction.getUiName());
addPrefixes(aLoadout, faction.getUiShortName());
for (final Modifier modifier : aLoadout.getAllModifiers()) {
addPrefixes(aLoadout, modifier.getDescription().getUiName());
}
}
/**
* Queries the index for a search string. It will match substrings of the indexed document and it will be case
* insensitive.
*
* @param aSearchString
* @return A {@link Collection} of {@link Loadout}s.
*/
public Collection<Loadout> query(String aSearchString) {
if (dirty) {
rebuild();
}
final List<Set<Loadout>> hits = new ArrayList<>();
for (final String part : aSearchString.toLowerCase().split(" ")) {
hits.add(invertedIndex.getOrDefault(part, Collections.EMPTY_SET));
}
hits.sort((l, r) -> l.size() - r.size());
final Iterator<Set<Loadout>> it = hits.iterator();
final Set<Loadout> ans = new HashSet<>(it.next());
while (it.hasNext()) {
ans.retainAll(it.next());
}
return ans;
}
/**
* Rebuilds the search index to take updated documents changes into the index.
*/
public void rebuild() {
final Set<Loadout> documents = documentsByKey(ALL_DOCUMENTS);
invertedIndex.clear();
for (final Loadout document : documents) {
merge(document);
}
dirty = false;
}
/**
* Removes the given loadout from the search index.
*
* An index rebuild is automatically performed on the next query if it has not been forced before the query.
*
* @param aLoadout
* The {@link Loadout} to remove from the index.
*/
public void unmerge(Loadout aLoadout) {
documentsByKey(ALL_DOCUMENTS).remove(aLoadout);
dirty = true;
}
/**
* Call when a document has been changed. Will cause a reindexing of all documents on the next query.
*/
public void update() {
dirty = true;
}
}
Here are the unit tests (github):
/*
* @formatter:off
* Li Song Mechlab - A 'mech building tool for PGI's MechWarrior: Online.
* Copyright (C) 2013 Emily Björk
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
//@formatter:on
package org.lisoft.lsml.model.search;
import static org.junit.Assert.*;
import static org.mockito.Mockito.*;
import java.util.*;
import org.junit.Test;
import org.lisoft.lsml.model.chassi.Chassis;
import org.lisoft.lsml.model.item.Faction;
import org.lisoft.lsml.model.loadout.Loadout;
import org.lisoft.lsml.model.modifiers.*;
/**
* Unit tests for {@link SearchIndex}.
*
* @author Emily Björk
*/
public class SearchIndexTest {
private final SearchIndex cut = new SearchIndex();
private final List<Modifier> modifiers = new ArrayList<>();
private Loadout makeLoadout() {
return makeLoadout(Faction.CLAN);
}
private Loadout makeLoadout(Faction aFaction) {
final Loadout l = mock(Loadout.class);
final Chassis c = mock(Chassis.class);
when(l.getChassis()).thenReturn(c);
when(l.getAllModifiers()).thenReturn(modifiers);
when(c.getFaction()).thenReturn(aFaction);
return l;
}
@Test
public void testModifiers() {
final ModifierDescription description = mock(ModifierDescription.class);
final Modifier modifier = mock(Modifier.class);
modifiers.add(modifier);
when(modifier.getDescription()).thenReturn(description);
when(description.getUiName()).thenReturn("ENERGY HEAT 5%");
final Loadout l = makeLoadout();
cut.merge(l);
final Collection<Loadout> ans = cut.query("ENERGY HEAT");
assertTrue(ans.contains(l));
assertEquals(1, ans.size());
}
@Test
public void testQueryAND() {
final Loadout l1 = makeLoadout();
when(l1.getName()).thenReturn("def abc");
cut.merge(l1);
final Loadout l2 = makeLoadout();
when(l2.getName()).thenReturn("ghi abc");
cut.merge(l2);
final Collection<Loadout> ans = cut.query("abc ghi");
assertFalse(ans.contains(l1));
assertTrue(ans.contains(l2));
}
@Test
public void testQueryByChassisMass() {
final Loadout l = makeLoadout();
when(l.getChassis().getMassMax()).thenReturn(95);
cut.merge(l);
final Collection<Loadout> ans = cut.query("95ton");
assertTrue(ans.contains(l));
assertEquals(1, ans.size());
}
@Test
public void testQueryByChassisMassSpace() {
final Loadout l = makeLoadout();
when(l.getChassis().getMassMax()).thenReturn(95);
cut.merge(l);
final Collection<Loadout> ans = cut.query("95 ton");
assertTrue(ans.contains(l));
assertEquals(1, ans.size());
}
@Test
public void testQueryByChassisName() {
final Loadout l = makeLoadout();
when(l.getChassis().getName()).thenReturn("ILYA MUROMETS");
cut.merge(l);
final Collection<Loadout> ans = cut.query("ILYA MUROMETS");
assertTrue(ans.contains(l));
assertEquals(1, ans.size());
}
@Test
public void testQueryByChassisSeries() {
final Loadout l = makeLoadout();
when(l.getChassis().getSeriesName()).thenReturn("SERIES");
cut.merge(l);
final Collection<Loadout> ans = cut.query("SERIES");
assertTrue(ans.contains(l));
assertEquals(1, ans.size());
}
@Test
public void testQueryByChassisShort() {
final Loadout l = makeLoadout();
when(l.getChassis().getShortName()).thenReturn("CPLT-K2");
cut.merge(l);
final Collection<Loadout> ans = cut.query("CPLT-K2");
assertTrue(ans.contains(l));
assertEquals(1, ans.size());
}
@Test
public void testQueryByFaction() {
final Loadout l = makeLoadout(Faction.CLAN);
cut.merge(l);
final Collection<Loadout> ans = cut.query(Faction.CLAN.getUiName());
assertTrue(ans.contains(l));
assertEquals(1, ans.size());
}
@Test
public void testQueryByFactionShort() {
final Loadout l = makeLoadout(Faction.INNERSPHERE);
cut.merge(l);
final Collection<Loadout> ans = cut.query(Faction.INNERSPHERE.getUiShortName());
assertTrue(ans.contains(l));
assertEquals(1, ans.size());
}
@Test
public void testQueryByName() {
final Loadout l = makeLoadout();
when(l.getName()).thenReturn("arbitrary string");
cut.merge(l);
final Collection<Loadout> ans = cut.query("arbitrary string");
assertTrue(ans.contains(l));
assertEquals(1, ans.size());
}
@Test
public void testQueryByNameCaseInsensitive() {
final Loadout l = makeLoadout();
when(l.getName()).thenReturn("abc");
cut.merge(l);
final Collection<Loadout> ans = cut.query("AB");
assertTrue(ans.contains(l));
}
@Test
public void testQueryByNamePrefix() {
final Loadout l = makeLoadout();
when(l.getName()).thenReturn("abc");
cut.merge(l);
final Collection<Loadout> ans2 = cut.query("ab");
assertTrue(ans2.contains(l));
final Collection<Loadout> ans1 = cut.query("a");
assertTrue(ans1.contains(l));
final Collection<Loadout> ans0 = cut.query("");
assertTrue(ans0.contains(l));
}
@Test
public void testQueryMultipleHits() {
final Loadout l1 = makeLoadout();
when(l1.getName()).thenReturn("def abc");
cut.merge(l1);
final Loadout l2 = makeLoadout();
when(l2.getName()).thenReturn("ghi abc");
cut.merge(l2);
final Collection<Loadout> ans = cut.query("abc");
assertTrue(ans.contains(l1));
assertTrue(ans.contains(l2));
}
/**
* A bug caused the index to be modified on queries because the smallest document set for any keyword was used
* directly without a copy when computing the intersection of all the document sets for the keywords.
*/
@Test
public void testQueryNoModifyIndex() {
final Loadout l1 = makeLoadout();
when(l1.getName()).thenReturn("x b");
cut.merge(l1);
final Loadout l2 = makeLoadout();
when(l2.getName()).thenReturn("x y");
cut.merge(l2);
final Loadout l3 = makeLoadout();
when(l3.getName()).thenReturn("a y");
cut.merge(l3);
cut.query("x y");
cut.query("x b");
cut.query("a y");
assertEquals(2, cut.query("x").size());
assertEquals(2, cut.query("y").size());
assertEquals(1, cut.query("a").size());
assertEquals(1, cut.query("b").size());
}
@Test
public void testRebuildEmpty() {
cut.rebuild();
final Collection<Loadout> ans = cut.query("");
assertTrue(ans.isEmpty());
}
@Test
public void testUnmerge() {
final Loadout l1 = makeLoadout();
when(l1.getName()).thenReturn("def abc");
cut.merge(l1);
final Loadout l2 = makeLoadout();
when(l2.getName()).thenReturn("ghi abc");
cut.merge(l2);
cut.unmerge(l2);
final Collection<Loadout> ans = cut.query("abc ghi");
assertTrue(ans.isEmpty());
}
@Test
public void testUnmergeEmptyIndex() {
final Loadout l2 = makeLoadout();
when(l2.getName()).thenReturn("abc");
cut.unmerge(l2);
final Collection<Loadout> ans = cut.query("abc");
assertTrue(ans.isEmpty());
}
@Test
public void testUpdate() {
final Loadout l = makeLoadout();
when(l.getName()).thenReturn("nope").thenReturn("hello");
cut.merge(l);
cut.update();
assertFalse(cut.query("nope").contains(l));
assertTrue(cut.query("hello").contains(l));
}
}
