Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік ғылым мәселесі
Computer science problem
Компьютерлік ғылымда екі немесе одан көп жолдың ең ұзын ортақ кіші жолы – бұл олардың барлығында кездесетін ең ұзын жол. Ең ұзын ортақ кіші жол бірнеше болуы мүмкін. Оның қолданылу аймақтарына деректерді дубликаттаудан құтылу және плагиатты анықтау жатады.
In computer science, a longest common substring of two or more strings is a longest string that is a substring of all of them. There may be more than one longest common substring. Applications include data deduplication and plagiarism detection.
Мәселе анықтамасы
Екі тізбек берілген, бірінің ұзындығы және екіншісінің ұзындығы , екеуінің де кіші тізбегі болатын ең ұзын тізбекті табыңыз. Бұл k ортақ кіші тізбек мәселесінің жалпылама түрі. Егер тізбектер жиынтығы берілген болса, , мұнда және әрқайсысы үшін кемінде тізбекте кіші тізбек ретінде кездесетін ең ұзын тізбекті табыңыз.
Given two strings, of length and of length , find a longest string which is substring of both and
A generalization is the k common substring problem. Given the set of strings , where and Find for each , a longest string which occurs as substring of at least strings.
Алгоритмдер
Жалпыландырылған жұрнақ ағашының көмегімен ең ұзақ ортақ кіші тізбектерінің ұзындығы мен бастапқы орнын табуға болады. Егер кіріс алфавитінің мөлшері болса, RAM сөздік есептеу моделінде жылдам алгоритмге қол жеткізуге болады. Атап айтқанда, бұл алгоритм келесі уақытта жұмыс істейді және келесі орынды пайдаланады. Динамикалық бағдарламалау арқылы мәселені шешуге кететін уақыт. Жалпыланған мәселенің шешімдері динамикалық бағдарламалау арқылы орын және уақыт алады, ал жалпыланған жұрнақ ағашымен уақыт алады.
One can find the lengths and starting positions of the longest common substrings of and in time with the help of a generalized suffix tree. A faster algorithm can be achieved in the word RAM model of computation if the size of the input alphabet is in In particular, this algorithm runs in time using space. Solving the problem by dynamic programming costs The solutions to the generalized problem take space and time with dynamic programming and take time with a generalized suffix tree.
Артықшылықтар ағашы
Таспалар жиынтығының ең ұзақ ортақ кіші тізбектерін табу үшін, осы таспаларға арналған жалпыланған жұрнақ ағашын құру керек, содан кейін астыңғы тармағындағы барлық таспалардан жапырақ түйіндері бар ең терең ішкі түйіндерді анықтау қажет. Оң жақтағы суретте "ABAB", "BABA" және "ABBA" таспаларының жұрнақ ағашы көрсетілген, олар бірегей таспалық терминаторлармен толықтырылып, "ABAB$0", "BABA$1" және "ABBA$2" болып алынған. "A", "B", "AB" және "BA" түйіндерінің барлығы 0, 1 және 2 нөмірленген барлық тізбектерден туындаған жапырақтарға ие. Жұрнақ ағашын құруға уақыт кетеді (егер әліпбидің мөлшері тұрақты болса). Егер ағаш төменнен жоғары қарай, әр түйіннің астында қандай тізбектер кездесетінін көрсететін бит векторымен қарастырылса, k ортақ кіші тізбектер мәселесі уақыт ішінде шешіледі. Егер жұрнақ ағашы ең төменгі ортақ ата-бабаны тұрақты уақытта табуға дайындалса, онда мәселені уақыт ішінде шешуге болады.
The longest common substrings of a set of strings can be found by building a generalized suffix tree for the strings, and then finding the deepest internal nodes which have leaf nodes from all the strings in the subtree below it. The figure on the right is the suffix tree for the strings "ABAB", "BABA" and "ABBA", padded with unique string terminators, to become "ABAB$0", "BABA$1" and "ABBA$2". The nodes representing "A", "B", "AB" and "BA" all have descendant leaves from all of the strings, numbered 0, 1 and 2. Building the suffix tree takes time (if the size of the alphabet is constant). If the tree is traversed from the bottom up with a bit vector telling which strings are seen below each node, the k common substring problem can be solved in time. If the suffix tree is prepared for constant time lowest common ancestor retrieval, it can be solved in time.