Быстрый способ найти общие слова между двумя строками

Question

У меня есть строка, которая имеет длину среднего предложения, она может состоять из любых случайных слов. У меня также есть файл (около 600kb), который содержит еще несколько случайных слов.

Я хочу найти общие слова между этими двумя как можно более эффективными. Прямо сейчас, я перехожу через две петли, чтобы сопоставить каждое слово из строки с каждым словом в файле, но это кажется немного неэффективным. Есть ли лучший и эффективный способ получить общие слова?

Answer 1

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

Если вы тестируете несколько предложений в отношении одного файла, загрузка файла в массив явно лучше. Если ваш файл больше вашей памяти (это не должно произойти действительно, а не с 600kb), тогда сделайте это наоборот.

В качестве альтернативы вы можете просто создать два массива, затем использовать array_intersect или array_intersect_key. Если PHP умный, array_intersect_keys будет использовать описанную выше процедуру; в любом случае это должно быть хорошо, потому что оно реализовано в C. Недостатком является то, что вы должны загружать все в память (опять же, вероятно, не проблема).

Answer 2

Ваша текущая сложность алгоритма - O (N * M). Чтобы улучшить его, вы можете использовать hashtable для хранения слов из файла. В PHP ассоциативные массивы реализуются как hashtables. Таким образом, ваш массив будет выглядеть следующим образом

$array = ['abc' => true, 'dfg' => true, ]// and so on 

и использовать array_key_exists, чтобы проверить, если слово в массиве. Это дает вам O (1) при проверке. И, наконец, вы должны повторять слова в своих предложениях. Это будет O (N), где N - количество слов. Конечная сложность - O (N)