Частично совпадают строки в случае List.contains (String)

Question

У меня есть List<String>

List<String> list = new ArrayList<String>();
list.add("ABCD");
list.add("EFGH");
list.add("IJ KL");
list.add("M NOP");
list.add("UVW X");

, если я list.contains("EFGH"), он возвращает true.Могу ли я получить правду в случае list.contains("IJ")?Я имею в виду, могу ли я частично сопоставить строки, чтобы найти их в списке?

У меня есть список из 15000 строк.И я должен проверить около 10000 строк, если они существуют в списке.Что может быть другим (более быстрым) способом сделать это?

Спасибо.

Answer 1

Если предложения от Roadrunner-EX не достаточно, то, я полагаю, вы ищете алгоритм Кнута-Морриса-Пратта .

Сложность времени:

• Временная сложность алгоритма таблицы O (n), время предварительной обработки
• Временная сложность алгоритма поиска составляет O (k)

Итак, сложность всего алгоритма составляет O (n + k).

• n = размер списка
• k = длина шаблона, который вы ищете

Обычный перебор будет иметь временную сложность O (нм)

Более того, алгоритм KMP будет иметь одинаковую сложность O (k) для поиска с той же самой строкой поиска, с другой стороны, он всегда будет O (км) для подхода грубой силы.

Answer 2

В качестве второго ответа, перечитав свой вопрос, вы также можете наследовать от интерфейса List, специализировать его только для Strings и переопределить метод contains ().

public class PartialStringList extends ArrayList<String>
{
    public boolean contains(Object o)
    {
        if(!(o instanceof String))
        {
            return false;
        }
        String s = (String)o;
        Iterator<String> iter = iterator();
        while(iter.hasNext())
        {
            String iStr = iter.next();
            if (iStr.contain(s))
            {
                return true;
            }
        }
        return false;
    }
}

Судя по вашим предыдущим комментариям, возможно, это не та скорость, которую вы ищете, но больше ли она похожа на ту, о которой вы просили?

Answer 3

Возможно, вы хотите поместить каждую группу String в HashSet, и по фрагменту я имею в виду не добавлять «IJ KL», а скорее добавлять «IJ» и «KL» отдельно.Если вам нужны как список, так и возможности поиска, вам может потребоваться сохранить две коллекции.

Answer 4

Вы можете использовать IterableUtils из Коллекции Apache Commons .

List<String> list = new ArrayList<String>();
list.add("ABCD");
list.add("EFGH");
list.add("IJ KL");
list.add("M NOP");
list.add("UVW X");

boolean hasString = IterableUtils.contains(list, "IJ", new Equator<String>() {
    @Override
    public boolean equate(String o1, String o2) {
        return o2.contains(o1);
    }

    @Override
    public int hash(String o) {
        return o.hashCode();
    }
});

System.out.println(hasString); // true

Answer 5

Да, вы можете! Вроде.

То, что вы ищете, часто называется нечеткий поиск или приблизительное совпадение строк , и существует несколько решений этой проблемы.

Например, с помощью библиотеки FuzzyWuzzy вы можете присвоить всем вашим строкам оценку в зависимости от того, насколько они похожи на конкретный поисковый запрос. Фактические значения кажутся целочисленными процентами от количества символов, совпадающих с длиной строки поиска.

После вызова FuzzySearch.extractAll вам решать, какой минимальный балл будет для строки, которая будет считаться совпадением.

Существуют также другие подобные библиотеки, которые стоит проверить, например google-diff-match-patch или API-интерфейс сходства текста Apache Commons и т. Д.

Если вам нужно что-то действительно сверхпрочное, ваш лучший выбор, вероятно, будет Lucene (как также упоминается Райан Шиллингтон )

Answer 6

Вот некоторый код, который использует регулярное выражение для сокращения внутреннего цикла, если нет тестовых строк найдено в целевой строке.

public static void main(String[] args) throws Exception {
    List<String> haystack = Arrays.asList(new String[] { "ABCD", "EFGH", "IJ KL", "M NOP", "UVW X" });
    List<String> needles = Arrays.asList(new String[] { "IJ", "NOP" });

    // To cut down on iterations, create one big regex to check the whole haystack
    StringBuilder sb = new StringBuilder();
    sb.append(".*(");
    for (String needle : needles) {
        sb.append(needle).append('|');
    }
    sb.replace(sb.length() - 1, sb.length(), ").*");
    String regex = sb.toString();

    for (String target : haystack) {
        if (!target.matches(regex)) {
            System.out.println("Skipping " + target);
            continue;
        }

        for (String needle : needles) {
            if (target.contains(needle)) {
                System.out.println(target + " contains " + needle);
            }
        }
    }
}

Выход:

Skipping ABCD
Skipping EFGH
IJ KL contains IJ
M NOP contains NOP
Skipping UVW X

Если вы действительно хотите стать милым, вы можете использовать бинарный поиск, чтобы определить, какие сегменты целевого списка совпадают, но это может не стоить этого.

Это зависит от того, насколько вероятно, что вы найдете хит. Низкие показатели попадания дадут хороший результат. Высокие показатели попадания будут работать не намного лучше, чем версия с простым вложенным циклом. рассмотрите возможность переворачивания петель, если одни иглы поражают множество целей, а другие - ни одной.

Это все об отмене пути поиска как можно скорее.

Answer 7

Как насчет:

java.util.List<String> list = new java.util.ArrayList<String>();
list.add("ABCD");
list.add("EFGH");
list.add("IJ KL");
list.add("M NOP");
list.add("UVW X");
java.util.regex.Pattern p = java.util.regex.Pattern.compile("IJ");
java.util.regex.Matcher m = p.matcher("");
for(String s : list)
{
    m.reset(s);
    if(m.find()) System.out.println("Partially Matched");
}

Answer 8

Вы можете выполнить итерации по списку, а затем вызывать в каждой строке String ().

public boolean listContainsString(List<string> list. String checkStr)
{
    Iterator<String> iter = list.iterator();
    while(iter.hasNext())
    {
        String s = iter.next();
        if (s.contain(checkStr))
        {
            return true;
        }
    }
    return false;
}

Мне кажется, что-то подобное должно работать.