Применение массива суффиксов (Suffix Array) при сопоставлении строк

алгоритм

предисловие

Сначала вопрос:给定300w字符串A, 之后给定80w字符串B, 需要求出 B中的每一个字符串, 是否是A中某一个字符串的子串. 也就是拿到80w个bool值.

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

В этот момент мы можем использоватьSuffix Arrayструктуру данных, чтобы помочь нам в этой задаче.

Введение в массив суффиксов

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

Массивы суффиксов были предложены Уди Манбером и Юджином Майерсом в 1990 году как более простая и компактная альтернатива деревьям суффиксов. Они также были независимо обнаружены Гастоном Гоннетом в 1987 году и названы «массивами PAT».

В 2016 году Ли Чжизе, Ли Цзянь и Хо Хунвэй предложили первый алгоритм построения массива суффиксов с оптимальной временной сложностью (линейное время) и пространственной сложностью (постоянное пространство), решив открытую проблему в этой области в течение 10 лет.

Давайте узнаем несколько концепций:

  • подстрока Подстрока r[i..j] строки S, iabcdefgПодстрока 0-3abc.
  • суффикс Суффикс    относится к специальной подстроке, начинающейся с позиции i и заканчивающейся в конце всей строки. Суффикс от i-го символа строки r обозначается как Suffix(i), то есть Suffix(i)=S[i...len(S)-1]. НапримерabcdefgизSuffix(5)заfg.
  • Массив суффиксов (SA[i] хранит индекс первого символа i-го по величине суффикса) Массив суффиксов SA — это одномерный массив, содержащий некоторую перестановку 1..n SA[1], SA[2], ..., SA[n] и гарантирующий, что Suffix(SA[i])
  • Ранговая группа (ранг[i] хранит приоритет суффикса(i)) Группа ранжирования Rank[i] сохраняет «ранг» суффикса (i) во всех суффиксах, расположенных от меньшего к большему.

Чувствуете ли вы легкую панику после прочтения вышеприведенных понятий? Не бойтесь, я тоже. Мы должны помнить, что мы инженеры и не играем в игры, поэтому нам не нужно реализовывать перфектный суффикс Следуйте моим идеям и используйте упрощенную версию массива суффиксов Исправьте проблему в преамбуле.

Идеи приложений

Прежде всего, примерно хочу понять истину.A является подстрокой B, тогда A является префиксом суффикса B. Напримерplдаappleподстрока . Тогда этоappleсуффиксpleприставкаpl.

Хорошо, давайте официально начнем собирать каштаны.

Буква A в названии содержит строки по 300 Вт. Давайте заменим ее на 4.

apple
orange
pear
banana

Буква B в названии имеет длину строки 80 ватт. Давайте заменим ее на единицу.

ear

.

Наша цель найтиearЯвляется ли это подстрокой одной из четырех строк в A. НайдитеTRUE/FALSE.

Затем мы сначала находим все строки и все подстроки в A. Помещаем их в массив.

НапримерappleВсе подстроки:

apple
pple
ple
le
e

Поместите все подстроки всех строк в A втот самыйМассив, а затем отсортируйте массив в соответствии с последовательностью строк.

Примечание. Чтобы оптимизировать эффективность сортировки, массив ортодоксальных суффиксов проделал большую работу и оптимизировал его с помощью более сложного алгоритма, но мой проект является офлайн-проектом, и сортировка миллионов занимает меньше минуты, поэтому меня зовут напрямуюArrays.sort.При необходимости вы можете обратиться к другим методам сортировки в Интернете, чтобы оптимизировать сортировку.

Например, если рассматривается только яблоко, порядок сортировки будет таким.

apple
e
le
ple
pple

Зачем сортировать?Для применения бинарного поиска эффективность бинарного поискаO(logN), очень отлично.

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

Код

package com.huyan.sa;

import java.util.*;

/**
 * Created by pfliu on 2019/12/28.
 */
public class SuffixArray {

    private List<String> array;


    /**
     * 用set构建一个后缀数组.
     */
    public static SuffixArray build(Set<String> stringSet) {
        SuffixArray sa = new SuffixArray();
        sa.array = new ArrayList<>(stringSet.size());
        // 求出每一个string的后缀
        for (String s : stringSet) {
            sa.array.addAll(suffixArray(s));
        }
        sa.array.sort(String::compareTo);
        return sa;
    }

    /**
     * 求单个字符串的所有后缀数组
     */
    private static List<String> suffixArray(String s) {
        List<String> sa = new ArrayList<>(s.length());
        for (int i = 0; i < s.length(); i++) {
            sa.add(s.substring(i));

        }
        return sa;
    }

    /**
     * 判断当前的后缀数组,是否有以s为前缀的.
     * 本质上: 判断s是否是构建时某一个字符串德子串.
     */
    public boolean saContains(String s) {
        int left = 0;
        int right = array.size() - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            String suffix = array.get(mid);
            int compareRes = compare1(suffix, s);
            if (compareRes == 0) {
                return true;
            } else if (compareRes < 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }

    /**
     * 比较两个字符串,
     * 1. 如果s2是s1的前缀返回0.
     * 2. 其余情况走string的compare逻辑.
     * 目的: 为了在string中使用二分查找,以及满足我们的,相等就结束的策略.
     */
    private static int compare1(String s1, String s2) {
        if (s1.startsWith(s2)) return 0;
        return s1.compareTo(s2);
    }

}

Реализация относительно проста, потому что это простой SA, который в основном делится на два метода:

  • build(Set): построить массив суффиксов из всех переданных строк.
  • saContains(String): определяет, является ли входящая строка префиксом суффикса (по сути, определяет, является ли входящая строка подстрокой определенной строки при построении).

оценивать

Делаем простую оценку производительности.

Оцените с помощью кода:

    @Test
    public void perf() throws IOException {
        // use sa
        long i = System.currentTimeMillis();
        List<String> A = Files.readAllLines(Paths.get("/Users/pfliu/data/old_data/A.txt"));
        SuffixArray sa = SuffixArray.build(new HashSet<>(A));

        int right = 0;
        int wrong = 0;
        List<String> B = Files.readAllLines(Paths.get("/Users/pfliu/data/old_data/B.txt"));
        for (String s : B) {
            if (sa.saContains(s)) {
                right++;
            } else {
                wrong++;
            }
        }
        log.info("use sa. all={}, right={}, wrong={}. time={}", B.size(), right, wrong, System.currentTimeMillis() - i);



        // violence
        wrong = 0;
        right = 0;
        //count
        int count = 0;
        long time = System.currentTimeMillis();
        for (String s : B) {
            boolean flag = false;
            for (String s1 : A) {
                if (s1.contains(s)) {
                    flag = true;
                    right++;
                    break;
                }
            }
            if (!flag) wrong++;
            if (++count % 1000 == 0) {
                log.info("use biolence. deal {} word. now right ={}, wrong ={}, time={}", count, right, wrong, System.currentTimeMillis() - time);
                time = System.currentTimeMillis();
            }
        }
    }

Вот выходная часть лога (я не стал дожидаться окончания работы решения грубой силы):

16:29:35.440 [main] INFO com.huyan.sa.SuffixArrayTest - use sa. all=815971, right=433402, wrong=382569. time=35371
16:29:49.748 [main] INFO com.huyan.sa.SuffixArrayTest - use biolence. deal 1000 word. now right =855, wrong =145, time=14301
16:30:11.807 [main] INFO com.huyan.sa.SuffixArrayTest - use biolence. deal 2000 word. now right =1625, wrong =375, time=22059
16:30:38.272 [main] INFO com.huyan.sa.SuffixArrayTest - use biolence. deal 3000 word. now right =2343, wrong =657, time=26465
16:31:07.080 [main] INFO com.huyan.sa.SuffixArrayTest - use biolence. deal 4000 word. now right =3019, wrong =981, time=28808
16:31:36.550 [main] INFO com.huyan.sa.SuffixArrayTest - use biolence. deal 5000 word. now right =3700, wrong =1300, time=29470
16:32:07.141 [main] INFO com.huyan.sa.SuffixArrayTest - use biolence. deal 6000 word. now right =4365, wrong =1635, time=30590
16:32:39.338 [main] INFO com.huyan.sa.SuffixArrayTest - use biolence. deal 7000 word. now right =5030, wrong =1970, time=32197
16:33:13.781 [main] INFO com.huyan.sa.SuffixArrayTest - use biolence. deal 8000 word. now right =5641, wrong =2359, time=34443
16:33:47.392 [main] INFO com.huyan.sa.SuffixArrayTest - use biolence. deal 9000 word. now right =6269, wrong =2731, time=33611
16:34:21.783 [main] INFO com.huyan.sa.SuffixArrayTest - use biolence. deal 10000 word. now right =6878, wrong =3122, time=34391

Мой оценочный набор: A=80 Вт, B=310 Вт.

Как видите, результаты жестокие.

использоватьSAПосле подсчета всех результатов требуется 35 с. Для решения методом полного перебора вычисление 1000 занимает 30 с.По мере работы программы процессорное время становится более напряженным, а также может постепенно замедляться.

В заключение

Видно, что в этой задаче эффективность SA сокрушительна по сравнению с решением грубой силы.

Следует подчеркнуть, что с этой «проблемой» я действительно столкнулся в своей работе.Попробовав насильственное решение, из-за низкой эффективности я использовал SA.30 для решения проблемы под руководством начальника.

Поэтому для некоторых часто используемых алгоритмов мы не должны придерживаться менталитета «я инженер, и я не участвую в соревнованиях по алгоритмам, это бесполезно», да, мы не считаем каждую секунду, как в соревнованиях по алгоритмам, но многие идеи алгоритма могут дать. Наша работа принесла большие улучшения.


Справочная статья

blog.CSDN.net/U013371163/…

zh.wikipedia.org/zh-hans/номер суффикса…

над.


свяжитесь со мной

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


ChangeLog

2019-12-28 Завершено

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

Добро пожаловать на перепечатку, пожалуйста, подпишите и сохраните исходную ссылку.

Контактный адрес электронной почты: huyanshi2580@gmail.com

Дополнительные заметки об обучении см. в личном блоге или подпишитесь на общедоступную учетную запись WeChat ------>Хуян тен

Категории