Алгоритм поиска синонимов - PullRequest
Новая
       22

Алгоритм поиска синонимов

6 голосов
/ 26 мая 2011

Я думаю, что пример будет намного лучше, чем описание в конце :) :)

Предположим, у нас есть массив массивов: 

("Server1", "Server_1", "Main Server", "192.168.0.3")
("Server_1", "VIP Server", "Main Server")
("Server_2", "192.168.0.4")
("192.168.0.3", "192.168.0.5")
("Server_2", "Backup")

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

("Server1", "Server_1", "Main Server", "192.168.0.3", "VIP Server", "192.168.0.5")
("Server_2", "192.168.0.4", "Backup")

Так что я думаю, что мне нужен своего рода рекурсивный алгоритм. Язык программирования на самом деле не имеет значения - мне нужно только немного помочь с идеей в целом. Я собираюсь использовать php или python.

Спасибо!

Ответы [ 4 ]

6 голосов
/ 26 мая 2011

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

Эффективным способом решения этой проблемы является выполнение алгоритма "заливки", которыйпо сути, рекурсивное дыхание, первый поиск.Эта запись в википедии описывает алгоритм заполнения потока и его применение для решения проблемы поиска связанных областей графика.

Чтобы увидеть, как исходный вопрос можно превратить в вопрос на графиках: сделайте каждую запись (например, «Сервер1», «Сервер_1» и т. Д.) Узлом на графике.Соедините узлы с ребрами тогда и только тогда, когда они являются синонимами.Матричная структура данных особенно подходит для отслеживания краев, если у вас достаточно памяти.В противном случае будет работать разреженная структура данных, такая как карта, тем более что число синонимов, вероятно, будет ограничено.

  • Сервер1 - это узел № 0
  • Сервер_1 - это узел № 1
  • Сервер_2 - это узел № 2

Тогда edge [0][1] = edge [1] [0] = 1, указывает на наличие ребра между узлами # 0 и # 1 (что означает, что они являются синонимами).Хотя edge [0] [2] = edge [2] [0] = 0, это означает, что Server1 и Server_2 являются , а не синонимами.

Анализ сложности

Создание этой структуры данных довольно эффективно, потому что для ее создания достаточно одного линейного прохода с поиском соответствия строк и номеров узлов.Если вы сохраняете сопоставление строк с номерами узлов в словаре, то это будет O (n log n) шаг.

Выполнение заливки равно O (n), вы посещаете каждый узел на графике только один раз.Итак, алгоритм всего O (n log n).

3 голосов
/ 26 мая 2011

Ввести целочисленную маркировку, которая обозначает группы синонимов. На старте отмечаются все слова с разными отметками от 1 до N.

Затем выполните поиск по своей коллекции, и если вы обнаружите, что два слова с индексами i и j являются синонимами, то отметьте все слова с пометкой i и j с меньшим числом обоих. После N итерации вы получите все группы синонимов.

Это какое-то грязное и не слишком эффективное решение, я считаю, что можно добиться большей производительности с помощью структур поиска объединения.

1 голос
/ 26 мая 2011

Это приведет к меньшей сложности, чем пример PHP (Python 3): 

a = [set(("Server1", "Server_1", "Main Server", "192.168.0.3")),
    set(("Server_1", "VIP Server", "Main Server")),
    set(("Server_2", "192.168.0.4")),
    set(("192.168.0.3", "192.168.0.5")),
    set(("Server_2", "Backup"))]

b = {}
c = set()
for s in a:
    full_s = s.copy()
    for d in s:
        if b.get(d):
            full_s.update(b[d])
    for d in full_s:
        b[d] = full_s
    c.add(frozenset(full_s))

for k,v in b.items():
    fsv = frozenset(v)
    if fsv in c:
        print(list(fsv))
        c.remove(fsv)
1 голос
/ 26 мая 2011

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

PHP, кажется, работает (по крайней мере, с данными изпример): 

$data = array(
    array("Server1", "Server_1", "Main Server", "192.168.0.3"),
    array("Server_1", "VIP Server", "Main Server"),
    array("Server_2", "192.168.0.4"),
    array("192.168.0.3", "192.168.0.5"),
    array("Server_2", "Backup"),
);

do {
    $foundSynonyms = false;
    foreach ( $data as $firstKey => $firstValue ) {
        foreach ( $data as $secondKey => $secondValue ) {
            if ( $firstKey === $secondKey ) {
                continue;
            }
            if ( array_intersect($firstValue, $secondValue) ) {
                $data[$firstKey] = array_unique(array_merge($firstValue, $secondValue));
                unset($data[$secondKey]);
                $foundSynonyms = true;
                break 2; // outer foreach
            }
        }
    }
} while ( $foundSynonyms );

print_r($data);

Вывод: 

Array
(
    [0] => Array
        (
            [0] => Server1
            [1] => Server_1
            [2] => Main Server
            [3] => 192.168.0.3
            [4] => VIP Server
            [6] => 192.168.0.5
        )

    [2] => Array
        (
            [0] => Server_2
            [1] => 192.168.0.4
            [3] => Backup
        )

)
...