Эффективный способ сравнения двух строк (упорядочение символов несуществен)

Question

Я пытаюсь найти алгоритм для сравнения двух строк. Он зарегистрировал бы совпадение с любыми словами, содержащими одни и те же буквы. Например, рента и крачка были бы эквивалентны, потому что они оба содержат буквы r, e, n, t.

EDIT Прошу прощения за то, что вы так расплывчаты. Сравнение будет сделано по двум наборам в несколько тысяч слов в сотни раз. Это всего лишь небольшая часть общего кода, поэтому я не хочу, чтобы он все сворачивал.

Для тех, кто просил, чтобы перебазировка была очень важна, например, аренда также соответствовала бы термальному.

РЕДАКТИРОВАТЬ 2 Для матча, такого как арендная плата == ternicate, ternicate не соответствует аренде. Это больше похоже на то, что слово два содержит буквы одного слова. Поэтому, если у вас есть дополнительные буквы, это все равно будет соответствовать, если слово содержит все буквы первого слова.

Answer 1

Хорошо, это действительно плохая идея, но это просто безумие, это может сработать!

1. Создайте список первых 26 простых чисел.

   primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, ...] 
   

2. Для каждой буквы слова найдите соответствующее простое число. A → 2, B → 3, C → 5 и т. Д.

3. Умножить эти простые числа вместе. В итоге вы получите (очень большое) число.

Слова, содержащие одинаковые буквы, будут иметь одинаковое число. Слова с разными буквами гарантированно имеют разные числа. Почему это?

Поскольку мы умножаем простые числа, мы всегда будем иметь уникальные продукты для уникальных комбинаций букв. Числа можно разложить обратно на их простые множители, и факторы говорят нам точно, какие буквы были в исходном слове. Порядок букв не сохраняется, но какие буквы были в слове и сколько было.

Например, возьмите слова «лицо» и «кафе».

FACE = 13 * 2 * 5 * 11 = 1430 
CAFE = 5 * 2 * 13 * 11 = 1430 

Ha! Что может быть более эффективным, чем простое целочисленное сравнение?

...

Хорошо, нет, может быть, нет. Это слишком смешно, чтобы на самом деле использовать. Но все же аккуратно.

Answer 2

Просто сначала сортируйте символы каждой строки, а затем сравните их.

rent == tern 
enrt == enrt 

Answer 3

Один из вариантов состоит в том, чтобы подсчитывать числа каждого символа в каждой строке и сравнивать подсчеты. Простая реализация должна принимать O(max(N, A)) время, где N - длина большей строки, а A - размер массива, который вы используете для хранения счетчиков. Например, в Java:

public boolean equalIgnoringOrder(String s1, String s2) { 
    if (s1.length() != s2.length()) { 
     return false; 
    } 
    // Assuming characters in the range ASCII 0 to 127 
    int[] c1 = new int[128]; 
    int[] c2 = new int[128]; 
    for (int i = 0; i < s1.length(); i++) { 
     c1[s1.charAt(i)]++; 
     c2[s2.charAt(i)]++; 
    } 
    for (int i = 0; i < c1.length; i++) { 
     if (c1[i] != c2[i]) { 
      return false; 
     } 
    } 
    return true; 
} 

Возможны некоторые улучшения. Например, вы можете справиться с произвольным набором символов, выполнив уменьшение диапазона; то есть выполнить начальный проход через s1 и s2, ища наименьшие и наибольшие символы в каждом из них, и использовать его для определения размера c1 и c2 и базового смещения. Это будет использовать меньше места в среднем и сократить время для инициализации массивов count. Он также предлагает короткое замыкание для сравнения; например когда самые маленькие и самые большие символы для s1 и s2 не совпадают.

Для сравнения, сравнение строк, отсортированных с использованием heapsort или quicksort, будет O(NlogN) в среднем с пространством O(N), где N - длина большей длины.

Однако, как указывает @pst, константы пропорциональности могут сделать алгоритм O(NlogN) или даже O(N*N) лучше алгоритма O(N), если N не велико. В этом случае средние длины сравниваемых строк, вероятно, являются наиболее важным фактором.

Приведенный выше код эффективно выполняет сортировку Radix с несколькими короткими замыканиями. (Три, если вы включаете короткое замыкание, связанное с уменьшением диапазона.) Таким образом, в конечном счете это сводится к тому, будет ли лучше сортировка быстрой сортировки/кучи или сортировка по радиусу. И это зависит от длины входных строк и диапазонов символов.

---

На другом уровне. @ В ответе Джона предлагается вычислить произведение простых чисел. Если мы сделаем вычисление с использованием произвольного представления точности, результирующие значения будут уникальными для каждого отдельного набора строк «равного игнорирования порядка». К сожалению, вычисление будет O(N*N). (Каждый промежуточный продукт имеет O(N) цифр, а умножение N-значного числа на константу - O(N). Сделайте это для N символов, и вы получите O(N*N).)

Но если мы сделаем вычисление по модулю (скажем) 64, результат будет действительно хорошим хешем, который нечувствителен к порядку символов; например

long hash = 1; 
for (int i = 0; i < s.length(); i++) { 
    hash = hash * primes[s.charAt(i)]; 
} 

Итак, я хотел бы утверждать, что алгоритм, который дает лучшую производительность и пространство использование в среднем для сравнения случайно генерируемых строк, вероятно, будет в форме:

if (s1.length() != s2.length()) { 
    return false; 
} 
if (hash(s1) != hash(s2)) { // computed as above 
    return false; 
} 
// Compare using sorting or character counting as above. 

---

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

Любой алгоритм, который делает менее 2 * N получений фидов или уточняющие менее 2 * N операции на принесенных значений в этом сценарии доказуемо неверна.

Answer 4

Ключевым моментом здесь, учитывая неопределенность в вопросе, является то, что он делает не представляется необходимым подсчитать, сколько раз появляется любая буква, только то, что он делает появляются.

Таким образом, если предположить, что все буквы в диапазоне a-z, а также при условии, что можно индексировать исходные списки слов в виде массива с использованием целочисленных индексов:

1. создать два массива (один для каждого списка).

2. для каждого слова в обоих списках вычисления битовой карты следующим образом:

bitmap = 0 
foreach (character in word) { 
    bitmap |= (1 << (character - 'a')) 
} 
arrayX[index] = bitmap; 

это растровый представляет собой набор букв, которые появляются в этом слове.

3. затем для каждого слова в множестве А, перебрать множество В, и матч, когда

arrayA[indexA] | arrayB[indexB] == arrayB[indexB] 

Этот тест будет только справедливо, если набор символов в этом слове А есть подмножество символов слово B. Операция «или» для битов - это эквивалент оператора объединения (∪) для вещественных множеств.

Смотрите статью в Википедии на set mathemtatics - А если и только если A ∪ B ⊆ B = B.

КСТАТИ Шаг 3 О (п^2), но все равно должны быть очень быстро, потому что это просто поразрядное сравнение. Несколько тысяч слов в каждом списке (~ 4M тестов) должны занимать менее секунды.

Answer 5

может быть, не fastet, но, вероятно, самый короткий решение с использованием Java + Google-коллекции + гуавы (для литья char[] ->List<Character>)

import com.google.common.collect.ImmutableMultiset; 
import com.google.common.primitives.Chars; 

public class EqualsOrderignore { 
private static boolean compareIgnoreOrder(final String s1, String s2) { 
    return ImmutableMultiset.copyOf(Chars.asList(s1.toCharArray())) 
      .equals(ImmutableMultiset.copyOf(Chars.asList(s2.toCharArray()))); 
} 
} 

выполнения этого алгоритма: O (s1.length + s2. длина)

Я вполне убежден, что это решение выполнит en-par с решением O (N1 + N2) ручной работы на VM-сервере.

как плюс это решение будет работать для любых экземпляров символов, а не только для a-Z.

Answer 6

Предполагая, что:

1. ваших слова состоят только из символов ASCII
2. случае не имеет значения
3. а соответствует ABCDE и ABCDE не соответствует а

Вы можете пройти матч string (s2) подсчет символов, затем пройти через значение (s1) и проверить, что все символы присутствуют в другом, что-то вроде (псевдокод, не отмечен):

boolean matches(String s1, String s2) { 
    int[] counts = new int[256]; 
    char[] c1; 
    char[] c2; 

    c1 = s1.getCharArray(); 
    c2 = c2.getCharArray(); 

    // count char occurences in longest string 
    for (int n = 0; n < c2.length; n++) { 
     counts[(int)c2[n]]++; 
    } 

    // check all chars in shortest string are foud in the longest 
    for (int n = 0; n < c1.length; n++) { 
     if (0 == counts[(int)c1[n]]) { 
      return false; 
     } 
    } 

    return true; 
} 

Это будет O (n) для суммы аргументов.

Редактировать: вопрос был изменен на асимметричную функцию между s1 и s2.

Answer 7

Я сделал много кода, который работал со словарями и анаграммами. Обычный подход состоит в том, чтобы преобразовать слово в отсортированный ключ, так что, как упоминалось выше, «аренда» соответствует «tern», потому что обе карты соответствуют «enrt».Однако, как только вы начнете с этого маршрута, становится действительно полезным иметь словарь символов и количество случаев. Вот некоторые питона код, который преобразует несортированный строку в словаре с (ключ = символ, значение = COUNT):

import collections 

# Create a defaultdict(int) from a string 
def create_collections_dict(key): 
    dk = collections.defaultdict(int) 
    for k in key: 
     dk[k] += 1 
    return dk 

Теперь вы можете набрать слова против других, мгновенно увидеть, сколько писем они имеют общие черты:

# Score the similarity of a defaultdict(int) against a string 
# (which is temporarily converted to a defaultdict(int)) 
def score(dk, cand) : 
    dc = create_collections_dict(cand) 
    return sum(min(dk[k], dc[k]) for k in dk.keys() if k in dc) 

if __name__ == '__main__': 
    base = create_collections_dict('rent') 
    for word in ['tern', 'ternicate', 'foobar']: 
     print word, score(base, word) 

Результаты:

tern 4 
ternicate 4 
foobar 1 

Answer 8

Я согласен со Стивеном C - это не достаточно хорошо определены, чтобы ответить.

Я не собираюсь ниспровергать, но не могли бы вы объяснить, например, насколько рента эквивалентна терпимости? У вас есть ответчики, которые полагают, что это так (люди думают, что количество случаев не имеет значения, и другие ответчики, которые принимают худшее. Одна из этих групп тратит свое время.

Кроме того, о производительности, нам нужно узнать больше о вашем шаблоне звонка. Не могли бы вы объяснить, будете ли вы рассматривать пару наборов более одного раза, или если наборы меняются?

И как терминологическое подергивание, вы уже можете Знайте это, но с текущей формулировкой ваш алгоритм не симметричен.

Вы говорите, что аренда будет соответствовать термальному, но, очевидно, тернарный не соответствует аренде. Итак, вы не действительно ищут эквивалентности. Вы ищете что-то вроде «находится в» или «можно сделать из».

Это означает, что вам нужно заботиться о заказе - вы получите разные результаты в зависимости от того, как вы посещаете свои комплекты.

Не поймите меня неправильно: это интересная проблема ... Я просто не знаю, в чем проблема.

Answer 9

Это довольно расплывчатое, но я хотел бы использовать ассоциативный массив, чтобы решить:

Используйте каждую букву каждое слова в качестве ключа к ассоциативному массиву целых чисел. Буквы одного слова увеличивают значения, а другие уменьшаются. Затем в конце вы можете запустить foreach через все ключи и проверить, что все значения равны нулю, а затем он соответствует. Это дает вам базовую арендную плату == tren.

Предостережения для неопределенности: 1. Если несколько букв в порядке, например rent == rreenntt, то при добавлении букв в массив проверьте, существует ли ключ, и если это так, не добавляйте его снова.
2. Если дополнительные буквы в порядке, например rent == renter, но fernt! = Renter, то при проверке значений массива в конце проверьте, что 1 и -1 не являются одновременно в массиве. Другими словами, 1 и 0 только в порядке, или -1 и 0 в порядке, но не 1 и -1 не могут быть в массиве одновременно.

Я не знаю, как быстро это было бы относительно других подходов, но было бы легко реализовать.

Answer 10

Я думаю, вы должны построить дерево. я написал немного кода Python, чтобы проиллюстрировать эту идею, но это, вероятно, багги:

class knot(): 
    def __init__(self, char, is_word, string = "" way = 0): 
     self.children = [] 
     self.shortest_way = way 
     self.char = char 
     self.word = is_word 
     self.string = string 

def comparing(strings): 
    sorted_strings = [] 
    for string in strings: 
     array_of_string = [] 
     for char in string: 
      array_of_string.append(char) 
     sorted_strings.append(array_of_string.sort()) 
    sorted_strings.sort() 

    start = [] 
    matches = [] 

    for array_of_string in sorted_strings: 
     matches += insert_string(array_of_string, start) 

def insert_string(array, start): 
    for match_string in test_string(array, start): 
     matches += (array, match_string.string) 
    add_string(array, start, 0): 

def add_string(array, knots, n): 
    minimum = 0 
    maximum = len(knots) - 1 
    while minimum != maximum: 
     num = int((minimum + maximum)/2) 
     if (knots[num].char > array[n]): 
      minimum = num 
     elif (knots[num].char < array[n]): 
      maximum = num 
     elif (knots[num].char == array[n]): 
      return add_string(array, knots[num], n+1) 
    knots.append(new_knots(array, n)) 
    knots.sort 

    """ more insertion routine needed""" 

def search_children(array, knots): 
    minimum = 0 
    maximum = len(knots) - 1 
    while minimum != maximum: 
     num = int((minimum + maximum)/2) 
     if (knots[num].char > array[0]): 
      minimum = num 
     elif (knots[num].char < array[0]): 
      maximum = num 
     elif (knots[num].char == array[0]): 
      return test_string(array, knots[num]) 
    return [] 

def test_string(array, target_knot): 
    if len(array) > target_knot.sortest_way + 1: 
     return [] 
    match_knots = [] 
    if len(array) == 1 and target_knot.is_word == True: 
     match_knots.append(target_knot) 
    for i in range(1, len(array)): 
     match_knots += search_children(array[i:], target_knot.children) 
    return match_knots 

Answer 11

Предполагая, что вы просто ищете для подмножеств, а ограничиваются общими английскими буквами, то эффективная гистограмма будет делать , Я бы посмотрел на использование 64-разрядного целого числа без знака, с 2 битами для подсчета до 2 вхождений, а дополнительные 12 бит для добавления флага переполнения и подсчета до трех вхождений «e t a o i n s r h l d». Биты заполняются, а не используются двоично (так что для трех «e» вы бы имели 111, иначе вам нужно что-то более сложное, чем двоичное & для проверки сдерживания). Чтобы проверить отношение подмножества, вы проверяете бит переполнения подмножества, которое вы тестируете, и если оно не установлено, вы можете просто поразмерно использовать и тестировать подмножество. Вернитесь к проверке O (Длина) отсортированного содержимого строки, если гистограмма переполнена.

Answer 12

Для любого алгоритма, который вы выбрали, может быть выполнена оптимизация для строк одинаковой длины. Все, что вам нужно сделать, это XOR каждый символ, если результат равен 0, то они содержат одни и те же буквы. Это не помогает в случае подстроки, но это может помочь короткому замыканию более дорогого сравнения.