Longest common subsequence problem (original) (raw)
مسألة أطول تسلسل مشترك (بالإنجليزية: Longest common subsequence problem) هي مشكلة إيجاد أطول تتابع مشترك لكل المتتاليات في مجموعة من المتسلسلات (متسلسلتين فقط في كثير من الأحيان) إنها تختلف عن مشكلة أخرى في إيجاد سلاسل فرعية، على عكس المتسلسلة الفرعية، المتسلسلات الجزئية لا تتطلب شغل مراتب متتالية داخل المتسلسلة الأصلية. مشكلة أطول تسلسل مشترك تعتبر مشكلة علوم حاسب كلاسيكية، ولها تطبيقات في المعلوماتية الحيوية. كما أنها تستخدم على نطاق واسع من قبل أنظمة التحكم مثل GIT للتوفيق بين العديد من التغيرات علي مجموعة من الملفات.
| Property | Value |
|---|---|
| dbo:abstract | مسألة أطول تسلسل مشترك (بالإنجليزية: Longest common subsequence problem) هي مشكلة إيجاد أطول تتابع مشترك لكل المتتاليات في مجموعة من المتسلسلات (متسلسلتين فقط في كثير من الأحيان) إنها تختلف عن مشكلة أخرى في إيجاد سلاسل فرعية، على عكس المتسلسلة الفرعية، المتسلسلات الجزئية لا تتطلب شغل مراتب متتالية داخل المتسلسلة الأصلية. مشكلة أطول تسلسل مشترك تعتبر مشكلة علوم حاسب كلاسيكية، ولها تطبيقات في المعلوماتية الحيوية. كما أنها تستخدم على نطاق واسع من قبل أنظمة التحكم مثل GIT للتوفيق بين العديد من التغيرات علي مجموعة من الملفات. (ar) Hledání nejdelší společné podposloupnosti je úloha z oboru matematické informatiky, jejíž podstatou je pro zadané posloupnosti nalézt nejdelší posloupnost, která je podposloupností obou dvou. Od příbuzného problému hledání nejdelšího společného podslova se liší tím, že podslovem se rozumí nepřerušený, souvislý sled v daných posloupnostech, zatímco podposloupnost může být s „přeskakováním prvků“. Podúloha hledání nejdelší společné podposloupnosti se objevuje při řadě jiných problémů. Je základem jedné z definice a také srovnávacích programů typu diff, které jsou dále rozvíjeny verzovacími systémy, jako je například Git. Řešení úlohy má rovněž aplikace v počítačové lingvistice a v bioinformatice. (cs) La plej longa komuna subvica problemo estas la serĉo por kompetenta maniero trovi la plej longan komunan (PLKS, LCS). Ĉi tiu komputika problemo jam gajnis elstarecon danke al sia estado en la biokomputika kampo. La eroj de subvico ne nepre devas esti sinsekvaj eroj de la fonto vico, tiel ekzemple BCDB estas subvico de ABCBDAB Ĝi devas ne esti konfuzita kun la .La diferenco estas en tio ke en la eroj nepre devas esti sinsekvaj eroj de la fonto vico, tiel ekzemple BCDB ne estas subĉeno de ABCBDAB Malnova maniero serĉi por subvicon estis per uzo de brutforta metodo: Estu donita vico X, difinu ĉiujn eblajn subvicojn de X, kaj kontrolu ĉu ĉiu subvico estis subvico de Y, konservante la plej longan trovitan subvicon. Ĉiu subvico de X respektivas al subaro de aro {1, 2, 3, 4, ...,k}. Tiel estas 2k subvicoj de X. Ĉi tio devus bezoni eksponentan tempon, farante ĉi tiu serĉon ege senefika por longaj vicoj, kiel fadeneroj de DNA de la homo. (eo) El problema de subsecuencia común más larga (en inglés, longest common subsequence problem, abreviado LCS problem), se trata de encontrar una subsecuencia más larga que es común en un conjunto de secuencias (Aunque en la mayor parte solamente se toman dos secuencias). Es diferente del problema de substring común más largo; a diferencia de los substrings, las subsecuencias no necesitan tener posiciones consecutivas en la secuencia original. El problema de LCS es uno de los problemas clásicos de las ciencias computacionales y es la base de programas que comparan datos como la utilidad diff, y ha tenido usos en bioinformática. También es usado ampliamente para los sistemas de control de revisión como Git para reconciliar múltiples cambios sobre archivos controlados de revisión. (es) The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in computational linguistics and bioinformatics. It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files. For example, consider the sequences (ABCD) and (ACBAD). They have 5 length-2 common subsequences: (AB), (AC), (AD), (BD), and (CD); 2 length-3 common subsequences: (ABD) and (ACD); and no longer common subsequences. So (ABD) and (ACD) are their longest common subsequences. (en) En informatique théorique, la plus longue sous-séquence commune à deux suites, ou deux chaînes de caractères, est une séquence étant sous-suite des deux suites, et étant de taille maximum. La résolution de ce problème peut être obtenue par programmation dynamique. La généralisation à un nombre arbitraire de suites est un problème NP-difficile. Le temps d'exécution de l'algorithme est exponentiel en nombre de séquences. (fr) 최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종 단 두 개중 하나가 되기도 한다.) 컴퓨터 과학에서 고전으로 통하는 문제이며, diff 유틸리티의 근간이 되며, 생물정보학에서도 많이 응용되고 있다. 이 문제는 연속되어 있는 공통 문자열을 찾는 최장 공통 부분문자열(longest common substring) 문제와 혼동해서는 안 된다. (ko) Il problema della massima sottosequenza comune (LCS, longest common subsequence) consiste nel trovare la più lunga sottosequenza comune a tutte le stringhe in un insieme di stringhe (solitamente due). Si noti che una sottosequenza non è necessariamente una sottostringa. Questo problema, classico tra i problemi informatici, trova applicazione in bioinformatica oltre ad essere anche la base di "diff" (un software di comparazione di file). (it) 最長共通部分列問題（さいちょうきょうつうぶぶんれつもんだい、英: Longest-common subsequence problem, LCS）とは、与えられた列の集合（しばしば、2つの列からなる集合）の最長共通部分列を見つけ出す問題である。（ここで部分列(subsequence)は、部分文字列(substring)とは異なることに注意する。前者は元の列の連続した項からなる必要はない。）例えば、「ABCX」と「AYBZC」との最長共通部分列は「ABC」である。この問題は計算機科学における古典的問題であり、diff などのファイル比較プログラムの基礎をなし、バイオインフォマティクスにも応用されている。 (ja) Najdłuższy wspólny podciąg (NWP, ang. longest common subsequence) – najdłuższy podciąg znaków, które występują w tej samej kolejności w dwóch porównywanych łańcuchach. Elementy podciągów nie muszą przy tym leżeć obok siebie (tym różni się ten problem od problemu najdłuższego wspólnego podłańcucha, ang. longest common substring). Rozwiązanie tego problemu jest bardzo przydatne przy pisaniu programów mających na celu wykrycie zmian w dokumentach lub plikach, lub przy pisaniu programów służących do identyfikacji plagiatów. Przykłady: * Dla ciągów abaabbaaa i babab ich NWP to baba i abab. * Dla ciągów POLITECHNIKA i TOALETA ich NWP to OLTA i OLEA. * Dla ciągów 123 oraz 543 ich NWP to 3. Warto przy tym zaznaczyć, że implementacja rozwiązania problemu może dotyczyć zarówno ciągu rozumianego jako ciąg liter, wyrazów czy nawet akapitów. (pl) Задача нахождения наибольшей общей подпоследовательности (англ. longest common subsequence, LCS) — задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух). Часто задача определяется как поиск всех наибольших подпоследовательностей. Это классическая задача информатики, которая имеет приложения, в частности, в задаче сравнения текстовых файлов (утилита diff), а также в биоинформатике. Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество её элементов (возможно пустое). Например, BCDB является подпоследовательностью последовательности ABCDBAB. Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей X и Y, если Z является подпоследовательностью как X, так и Y. Требуется для двух последовательностей X и Y найти общую подпоследовательность наибольшей длины. Заметим, что НОП может быть несколько. Обратите внимание! Подпоследовательность отличается от подстроки. Например, если есть исходная последовательность «ABCDEF», то «ACE» будет подпоследовательностью, но не подстрокой, а «ABC» будет как подпоследовательностью, так и подстрокой. (ru) Пошук найдовшої спільної підпослідовності (англ. longest common subsequence, LCS) — це завдання пошуку послідовності, яка є підпослідовністю кількох послідовностей (зазвичай — двох). Часто завдання визначається як пошук всіх найбільших спільних підпослідовностей. Ця задача відрізняється від пошуку найдовшого спільного підрядка: на відміну від підрядків, підпослідовності не повинні займати суміжні позиції в оригінальних послідовностях. Це класична задача інформатики, яка має застосування, зокрема, в задачі порівняння текстових файлів (утиліта diff), а також у біоінформатиці. Підпослідовність можна отримати з деякої послідовності, якщо видалити з неї деяку множину елементів (можливо, порожню). Наприклад, BCDB є підпослідовністю послідовності ABCDBAB. Також вона буде підпослідовністю послідовності XBXCDXBX. Послідовність Z є спільною підпослідовність послідовностей X і Y, якщо Z є підпослідовністю як X, так і Y. Потрібно для двох послідовностей X і Y знайти спільну підпослідовність найбільшої довжини. Зауважимо, що таких підпослідовностей може бути кілька. (uk) 最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的問題。这与查找最長公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题，也是程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Nubio_Diff_Screenshot3.png?width=300 |
| dbo:wikiPageExternalLink | https://www.codespeedy.com/find-longest-common-subsequence-in-python/ https://xlinux.nist.gov/dads/HTML/longestCommonSubsequence.html http://rosettacode.org/wiki/Longest_common_subsequence |
| dbo:wikiPageID | 236105 (xsd:integer) |
| dbo:wikiPageLength | 36112 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123640672 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Memoization dbr:Method_of_Four_Russians dbc:Dynamic_programming dbr:Levenshtein_distance dbc:NP-complete_problems dbr:Quadratic_growth dbr:Git_(software) dbr:NP-hard dbr:Optimal_substructure dbr:Subsequence dbr:Computational_linguistics dbr:Computer_science dbr:Data_comparison dbr:Hash_collision dbr:Hash_function dbc:Combinatorics dbc:Polynomial-time_problems dbr:Dynamic_programming dbr:Checksum dbc:Problems_on_strings dbr:Chvátal–Sankoff_constants dbr:Hirschberg's_algorithm dbr:Revision_control dbr:Backtracking dbr:Hunt–Szymanski_algorithm dbr:Shortest_common_supersequence_problem dbr:Big_O_notation dbr:Bioinformatics dbr:Edit_distance dbr:Tracy–Widom_distribution dbr:Diff dbr:Diff_utility dbr:Longest_alternating_subsequence dbr:Longest_common_substring_problem dbr:Longest_increasing_subsequence dbr:Overlapping_subproblems dbr:Merge_(revision_control) dbr:Cache-oblivious dbr:File:Nubio_Diff_Screenshot3.png |
| dbp:wikiPageUsesTemplate | dbt:Distinguish dbt:Harvtxt dbt:Main dbt:Reflist dbt:Short_description dbt:Unreferenced_section dbt:Wikibooks dbt:Strings |
| dct:subject | dbc:Dynamic_programming dbc:NP-complete_problems dbc:Combinatorics dbc:Polynomial-time_problems dbc:Problems_on_strings |
| gold:hypernym | dbr:Problem |
| rdf:type | owl:Thing yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Event100029378 yago:GrammaticalRelation113796779 yago:Inflection113803782 yago:LinguisticRelation113797142 yago:Paradigm113804375 yago:Problem114410605 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:Relation100031921 yago:YagoPermanentlyLocatedEntity dbo:Disease yago:Rule105846932 yago:State100024720 yago:WikicatAlgorithmsOnStrings yago:WikicatPolynomial-timeProblems yago:WikicatProblemsOnStrings yago:WikicatProgrammingParadigms |
| rdfs:comment | مسألة أطول تسلسل مشترك (بالإنجليزية: Longest common subsequence problem) هي مشكلة إيجاد أطول تتابع مشترك لكل المتتاليات في مجموعة من المتسلسلات (متسلسلتين فقط في كثير من الأحيان) إنها تختلف عن مشكلة أخرى في إيجاد سلاسل فرعية، على عكس المتسلسلة الفرعية، المتسلسلات الجزئية لا تتطلب شغل مراتب متتالية داخل المتسلسلة الأصلية. مشكلة أطول تسلسل مشترك تعتبر مشكلة علوم حاسب كلاسيكية، ولها تطبيقات في المعلوماتية الحيوية. كما أنها تستخدم على نطاق واسع من قبل أنظمة التحكم مثل GIT للتوفيق بين العديد من التغيرات علي مجموعة من الملفات. (ar) El problema de subsecuencia común más larga (en inglés, longest common subsequence problem, abreviado LCS problem), se trata de encontrar una subsecuencia más larga que es común en un conjunto de secuencias (Aunque en la mayor parte solamente se toman dos secuencias). Es diferente del problema de substring común más largo; a diferencia de los substrings, las subsecuencias no necesitan tener posiciones consecutivas en la secuencia original. El problema de LCS es uno de los problemas clásicos de las ciencias computacionales y es la base de programas que comparan datos como la utilidad diff, y ha tenido usos en bioinformática. También es usado ampliamente para los sistemas de control de revisión como Git para reconciliar múltiples cambios sobre archivos controlados de revisión. (es) En informatique théorique, la plus longue sous-séquence commune à deux suites, ou deux chaînes de caractères, est une séquence étant sous-suite des deux suites, et étant de taille maximum. La résolution de ce problème peut être obtenue par programmation dynamique. La généralisation à un nombre arbitraire de suites est un problème NP-difficile. Le temps d'exécution de l'algorithme est exponentiel en nombre de séquences. (fr) 최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종 단 두 개중 하나가 되기도 한다.) 컴퓨터 과학에서 고전으로 통하는 문제이며, diff 유틸리티의 근간이 되며, 생물정보학에서도 많이 응용되고 있다. 이 문제는 연속되어 있는 공통 문자열을 찾는 최장 공통 부분문자열(longest common substring) 문제와 혼동해서는 안 된다. (ko) Il problema della massima sottosequenza comune (LCS, longest common subsequence) consiste nel trovare la più lunga sottosequenza comune a tutte le stringhe in un insieme di stringhe (solitamente due). Si noti che una sottosequenza non è necessariamente una sottostringa. Questo problema, classico tra i problemi informatici, trova applicazione in bioinformatica oltre ad essere anche la base di "diff" (un software di comparazione di file). (it) 最長共通部分列問題（さいちょうきょうつうぶぶんれつもんだい、英: Longest-common subsequence problem, LCS）とは、与えられた列の集合（しばしば、2つの列からなる集合）の最長共通部分列を見つけ出す問題である。（ここで部分列(subsequence)は、部分文字列(substring)とは異なることに注意する。前者は元の列の連続した項からなる必要はない。）例えば、「ABCX」と「AYBZC」との最長共通部分列は「ABC」である。この問題は計算機科学における古典的問題であり、diff などのファイル比較プログラムの基礎をなし、バイオインフォマティクスにも応用されている。 (ja) 最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的問題。这与查找最長公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题，也是程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。 (zh) Hledání nejdelší společné podposloupnosti je úloha z oboru matematické informatiky, jejíž podstatou je pro zadané posloupnosti nalézt nejdelší posloupnost, která je podposloupností obou dvou. Od příbuzného problému hledání nejdelšího společného podslova se liší tím, že podslovem se rozumí nepřerušený, souvislý sled v daných posloupnostech, zatímco podposloupnost může být s „přeskakováním prvků“. (cs) La plej longa komuna subvica problemo estas la serĉo por kompetenta maniero trovi la plej longan komunan (PLKS, LCS). Ĉi tiu komputika problemo jam gajnis elstarecon danke al sia estado en la biokomputika kampo. La eroj de subvico ne nepre devas esti sinsekvaj eroj de la fonto vico, tiel ekzemple BCDB estas subvico de ABCBDAB Ĝi devas ne esti konfuzita kun la .La diferenco estas en tio ke en la eroj nepre devas esti sinsekvaj eroj de la fonto vico, tiel ekzemple BCDB ne estas subĉeno de ABCBDAB Malnova maniero serĉi por subvicon estis per uzo de brutforta metodo: (eo) The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in computational linguistics and bioinformatics. It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files. (en) Najdłuższy wspólny podciąg (NWP, ang. longest common subsequence) – najdłuższy podciąg znaków, które występują w tej samej kolejności w dwóch porównywanych łańcuchach. Elementy podciągów nie muszą przy tym leżeć obok siebie (tym różni się ten problem od problemu najdłuższego wspólnego podłańcucha, ang. longest common substring). Rozwiązanie tego problemu jest bardzo przydatne przy pisaniu programów mających na celu wykrycie zmian w dokumentach lub plikach, lub przy pisaniu programów służących do identyfikacji plagiatów. Przykłady: (pl) Задача нахождения наибольшей общей подпоследовательности (англ. longest common subsequence, LCS) — задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух). Часто задача определяется как поиск всех наибольших подпоследовательностей. Это классическая задача информатики, которая имеет приложения, в частности, в задаче сравнения текстовых файлов (утилита diff), а также в биоинформатике. (ru) Пошук найдовшої спільної підпослідовності (англ. longest common subsequence, LCS) — це завдання пошуку послідовності, яка є підпослідовністю кількох послідовностей (зазвичай — двох). Часто завдання визначається як пошук всіх найбільших спільних підпослідовностей. Ця задача відрізняється від пошуку найдовшого спільного підрядка: на відміну від підрядків, підпослідовності не повинні займати суміжні позиції в оригінальних послідовностях. Це класична задача інформатики, яка має застосування, зокрема, в задачі порівняння текстових файлів (утиліта diff), а також у біоінформатиці. (uk) |
| rdfs:label | أطول تسلسل مشترك (رياضيات) (ar) Hledání nejdelší společné podposloupnosti (cs) Plej longa komuna subvica problemo (eo) Problema de subsecuencia común más larga (es) Plus longue sous-séquence commune (fr) Massima sottosequenza comune (it) Longest common subsequence problem (en) 최장 공통 부분 수열 (ko) 最長共通部分列問題 (ja) Najdłuższy wspólny podciąg (pl) Наибольшая общая подпоследовательность (ru) 最长公共子序列 (zh) Пошук найдовшої спільної підпослідовності (uk) |
| owl:differentFrom | dbr:Longest_common_substring_problem |
| owl:sameAs | freebase:Longest common subsequence problem yago-res:Longest common subsequence problem wikidata:Longest common subsequence problem dbpedia-ar:Longest common subsequence problem dbpedia-be:Longest common subsequence problem dbpedia-cs:Longest common subsequence problem dbpedia-eo:Longest common subsequence problem dbpedia-es:Longest common subsequence problem dbpedia-fa:Longest common subsequence problem dbpedia-fr:Longest common subsequence problem dbpedia-it:Longest common subsequence problem dbpedia-ja:Longest common subsequence problem dbpedia-ka:Longest common subsequence problem dbpedia-ko:Longest common subsequence problem dbpedia-pl:Longest common subsequence problem dbpedia-ru:Longest common subsequence problem dbpedia-sr:Longest common subsequence problem http://ta.dbpedia.org/resource/பொதுவான_நீண்ட_துணைத்தொடர்_புதிர் dbpedia-uk:Longest common subsequence problem dbpedia-vi:Longest common subsequence problem dbpedia-zh:Longest common subsequence problem https://global.dbpedia.org/id/QkDE |
| prov:wasDerivedFrom | wikipedia-en:Longest_common_subsequence_problem?oldid=1123640672&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Nubio_Diff_Screenshot3.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Longest_common_subsequence_problem |
| is dbo:wikiPageDisambiguates of | dbr:LCS |
| is dbo:wikiPageRedirects of | dbr:LCS_problem dbr:Lcs_problem dbr:Difference_Algorithm dbr:Longest-common_subsequence_problem dbr:Longest_common_subsequence |
| is dbo:wikiPageWikiLink of | dbr:Pretty_Diff dbr:List_of_algorithms dbr:MUMmer dbr:David_Sankoff dbr:Index_of_combinatorics_articles dbr:Levenshtein_distance dbr:Dan_Hirschberg dbr:Optimal_substructure dbr:Computational_biology dbr:Time_Warp_Edit_Distance dbr:Václav_Chvátal dbr:Jewels_of_Stringology dbr:Dynamic_programming dbr:File_comparison dbr:DiffEngineX dbr:Hirschberg's_algorithm dbr:List_of_NP-complete_problems dbr:Jaro–Winkler_distance dbr:Hunt–Szymanski_algorithm dbr:Shortest_common_supersequence_problem dbr:Edit_distance dbr:Diff dbr:Diff-Text dbr:Longest_alternating_subsequence dbr:Longest_increasing_subsequence dbr:ROUGE_(metric) dbr:LCS dbr:LCS_problem dbr:Lcs_problem dbr:Difference_Algorithm dbr:Longest-common_subsequence_problem dbr:Longest_common_subsequence |
| is owl:differentFrom of | dbr:Longest_common_substring_problem |
| is foaf:primaryTopic of | wikipedia-en:Longest_common_subsequence_problem |
