Самый эффективный способ найти количество совпадений строки с массивом слов?

Question

допустим, у меня есть строка

String test = "This is a test string and I have some stopwords in here";

, и я хочу увидеть, сколько раз слова в массиве ниже соответствуют моей строке

псевдокод

array = a,and,the,them,they,I

так что ответ будет "3"

просто интересно, какой самый эффективный способ сделать это в Java?

Answer 1

Как то так? Не уверен насчет «самого эффективного», но достаточно простого.

Set<String> s1 = new HashSet<String>(Arrays.asList("This is a test string and I have some stopwords in here".split("\\s")));
Set<String> s2 = new HashSet<String>(Arrays.asList("a", "and", "the", "them", "they", "I"));
s1.retainAll(s2);
System.out.println(s1.size());

Просто пересечение двух наборов слов.

Answer 2

Я бы, вероятно, сохранил слова во входных данных в HashSet, а затем прошел бы итерацию по массиву и посмотрел бы, содержится ли каждое слово в массиве .conset в наборе.. Ввод " Вокруг света за 80 дней ".

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main
{
    public static void main(final String[] argv)
        throws FileNotFoundException
    {
        final File     file;
        final String[] wordsToFind;

        file        = new File(argv[0]);
        wordsToFind = getWordsToFind(file);
        a(file, wordsToFind);
        b(file, wordsToFind);
        c(file, wordsToFind);
        d(file, wordsToFind);
    }

    // this just reads the file into the disk cache
    private static String[] getWordsToFind(final File file)
        throws FileNotFoundException
    {
        final Scanner     scanner;
        final Set<String> words;

        scanner = new Scanner(file);
        words   = new HashSet<String>();

        while(scanner.hasNext())
        {
            final String word;

            word = scanner.next();
            words.add(word);
        }

        return (words.toArray(new String[words.size()]));
    }

    // bad way, read intpo a list and then iterate over the list until you find a match
    private static void a(final File     file,
                          final String[] wordsToFind)
        throws FileNotFoundException
    {
        final long start;
        final long end;
        final long total;
        final Scanner      scanner;
        final List<String> words;
        int                matches;

        scanner = new Scanner(file);
        words   = new ArrayList<String>();

        while(scanner.hasNext())
        {
            final String word;

            word = scanner.next();
            words.add(word);
        }

        start = System.nanoTime();

        {
            matches = 0;

            for(final String wordToFind : wordsToFind)
            {
                for(final String word : words)
                {
                    if(word.equals(wordToFind))
                    {
                        matches++;
                        break;
                    }
                }
            }

            System.out.println(matches);
        }

        end   = System.nanoTime();
        total = end - start;
        System.out.println("a: " + total);
    }

    // slightly better way, read intpo a list and then iterate over the set (which reduces the number of things you progbably
    // have to read until you find a match), until you find a match
    private static void b(final File     file,
                          final String[] wordsToFind)
        throws FileNotFoundException
    {
        final long start;
        final long end;
        final long total;
        final Scanner     scanner;
        final Set<String> words;
        int               matches;

        scanner = new Scanner(file);
        words   = new HashSet<String>();

        while(scanner.hasNext())
        {
            final String word;

            word = scanner.next();
            words.add(word);
        }

        start = System.nanoTime();

        {
            matches = 0;

            for(final String wordToFind : wordsToFind)
            {
                for(final String word : words)
                {
                    if(word.equals(wordToFind))
                    {
                        matches++;
                        break;
                    }
                }
            }

            System.out.println(matches);
        }

        end   = System.nanoTime();
        total = end - start;
        System.out.println("b: " + total);
    }

    // my way
    private static void c(final File     file,
                          final String[] wordsToFind)
        throws FileNotFoundException
    {
        final long start;
        final long end;
        final long total;
        final Scanner     scanner;
        final Set<String> words;
        int               matches;

        scanner = new Scanner(file);
        words   = new HashSet<String>();

        while(scanner.hasNext())
        {
            final String word;

            word = scanner.next();
            words.add(word);
        }

        start = System.nanoTime();

        {
            matches = 0;

            for(final String wordToFind : wordsToFind)
            {
                if(words.contains(wordToFind))
                {
                    matches++;
                }
            }

            System.out.println(matches);
        }

        end   = System.nanoTime();
        total = end - start;
        System.out.println("c: " + total);
    }

    // Nikita Rybak way
    private static void d(final File     file,
                          final String[] wordsToFind)
        throws FileNotFoundException
    {
        final long start;
        final long end;
        final long total;
        final Scanner     scanner;
        final Set<String> words;
        int               matches;

        scanner = new Scanner(file);
        words   = new HashSet<String>();

        while(scanner.hasNext())
        {
            final String word;

            word = scanner.next();
            words.add(word);
        }

        start = System.nanoTime();

        {
            words.retainAll(new HashSet<String>(Arrays.asList(wordsToFind)));
            matches = words.size();
            System.out.println(matches);
        }

        end   = System.nanoTime();
        total = end - start;
        System.out.println("d: " + total);
    }
}

Результаты (после нескольких прогонов каждый прогон во многом одинаков):

12596
a: 2440699000
12596
b: 2531635000
12596
c: 4507000
12596
d: 5597000

Если вы измените его, добавив «XXX» к каждому слову в getWordsToFind (чтобы слова не были найдены), вы получите:

0
a: 7415291000
0
b: 4688973000
0
c: 2849000
0
d: 7981000

И, для полноты, я попробовал его, просто ищаслово «я», и результаты:

1
a: 235000
1
b: 351000
1
c: 75000
1
d: 10725000

Answer 3

самое эффективное, что нужно сделать, это отсортировать оба 'test' и 'array', а затем выполнить итерации по обоим: n.log (n) + n

test -> ['a', 'and', 'have', 'here', in, is, ..., 'This'] массив -> ['a', 'and', 'the', 'them', 'они', 'I']

совпадения теста массива 'a' 'a' 1 «а» и «1 'и' 'и' 2 'и' 'есть' 2 «здесь» 2 '' в '2 «это» 2 ...

Answer 4

сохраните ваши строки в хеш-таблице (HashMap of (String and Integer)), затем выполните итерацию по тексту и увеличьте целочисленное значение для соответствующего слова в хеш-таблице. затем итерация по хеш-таблице и суммирование всех целочисленных значений.

Answer 5

Незначительное изменение в ответе Никиты (до 1 для Никиты).Если вы используете List для s1, вы получите количество вхождений (в случае, если слово встречается в предложении несколько раз).

List<String> s1 = new ArrayList<String>(Arrays.asList("This is a test string and I have some stopwords in here".split("\\s")));
Set<String> s2 = new HashSet<String>(Arrays.asList("a", "and", "the", "them", "they", "I"));
s1.retainAll(s2);
System.out.println(s1.size());