检索结果-内蒙古大学图书馆

您好，读者！请登录

内蒙古大学图书馆

首页
概况
党建
资源
服务
科研支持
- 论文收录引用证明
- 科技查新
知识产权
档案馆
帮助

咨询与建议

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入0个字，您还可以输入200个字

全部搜索
期刊论文
图书
学位论文
标准
纸本馆藏
外文资源发现
数据库导航
超星发现

高级检索

时间限定

出版年份：

文献类型

图书期刊文献学位论文多媒体

馆藏选择

电子馆藏纸本馆藏

核心期刊

全部期刊 SCI 收录期刊 SSCI 收录期刊 EI 收录期刊 CSCD 收录期刊 CSSCI 收录期刊

语言

中文英文

文献类型

期刊文献图书学位论文标准纸本馆藏

帮助

文字说明：

T=题名（书名、题名），A=作者（责任者），K=主题词，P=出版物名称，PU=出版社名称，O=机构（作者单位、学位授予单位、专利申请人），L=中图分类号，C=学科分类号，U=全部字段，Y=年（出版发行年、学位年度、标准发布年）

检索规则说明：

AND代表“并且”；OR代表“或者”；NOT代表“不包含”；(注意必须大写,运算符两边需空一格)

检索范例：

范例一：(K=图书馆学 OR K=情报学) AND A=范并思 AND Y=1982-2016
范例二：P=计算机应用与软件 AND (U=C++ OR U=Basic) NOT K=Visual AND Y=2011-2016

分类表

所选分类

>> <<

限定检索结果

文献类型

99 篇 期刊文献
48 篇 会议
2 篇 学位论文

馆藏范围

149 篇 电子文献
0 种 纸本馆藏

日期分布

学科分类号

126 篇 工学
- 122 篇 计算机科学与技术...
- 30 篇 软件工程
- 8 篇 电气工程
- 4 篇 控制科学与工程
- 2 篇 信息与通信工程
- 2 篇 生物医学工程（可授...
- 1 篇 机械工程
- 1 篇 仪器科学与技术
- 1 篇 电子科学与技术（可...
- 1 篇 测绘科学与技术
- 1 篇 生物工程
- 1 篇 网络空间安全
73 篇 理学
- 70 篇 数学
- 3 篇 生物学
- 1 篇 化学
- 1 篇 系统科学
- 1 篇 统计学（可授理学、...
4 篇 管理学
- 4 篇 管理科学与工程(可...
3 篇 法学
- 3 篇 法学
1 篇 农学
- 1 篇 作物学

主题

149 篇 string algorithm...
16 篇 suffix trees
15 篇 pattern matching
11 篇 combinatorial pr...
8 篇 palindromes
7 篇 longest common s...
7 篇 approximate stri...
6 篇 word-level paral...
6 篇 approximation al...
6 篇 parikh vectors
6 篇 data structures
6 篇 dynamic programm...
6 篇 edit distance
5 篇 parallel algorit...
5 篇 hamming distance
5 篇 burrows-wheeler ...
5 篇 suffix sorting
5 篇 suffix array
5 篇 combinatorics on...
4 篇 repetitions

机构

11 篇 cwi
9 篇 vrije univ
9 篇 kings coll londo...
7 篇 univ helsinki de...
7 篇 bar ilan univ de...
7 篇 kyushu univ dept...
7 篇 univ cent florid...
5 篇 univ cent florid...
4 篇 univ wisconsin d...
4 篇 louisiana state ...
4 篇 johns hopkins un...
4 篇 univ haifa cri i...
4 篇 kings coll londo...
3 篇 univ warsaw inst...
3 篇 univ eastern fin...
3 篇 bar ilan univ de...
3 篇 lodz univ techno...
3 篇 shenkar coll dep...
3 篇 univ warwick dep...
3 篇 facebook inc men...

作者

18 篇 pissis solon p.
10 篇 inenaga shunsuke
8 篇 amir amihood
7 篇 loukides grigori...
7 篇 charalampopoulos...
7 篇 bannai hideo
7 篇 thankachan sharm...
7 篇 grabowski szymon
6 篇 sweering michell...
6 篇 takeda masayuki
6 篇 giaquinta emanue...
6 篇 liptak zsuzsanna
6 篇 bernardini giuli...
6 篇 stougie leen
5 篇 fici gabriele
5 篇 ganguly arnab
5 篇 abedin paniz
5 篇 nakashima yuto
5 篇 mieno takuya
5 篇 thankachan sharm...

语言

132 篇 英文
17 篇 其他

检索条件"主题词=String algorithms"

共 149 条记录，以下是111-120 订阅

全选清除本页清除全部题录导出标记到"检索档案"

详细简洁

排序：

Optimal algorithms for Bounded Weighted Edit Distance 64

Optimal Algorithms for Bounded Weighted Edit Distance

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Cassis, Alejandro Kociumaka, Tomasz Wellnitz, Philip Saarland Univ Saarland Informat Campus Saarbrucken Germany Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany

ISBN: (纸本)9798350318944

The edit distance (also known as Levenshtein distance) of two strings is the minimum number of insertions, deletions, and substitutions of characters needed to transform one string into the other. The textbook dynamic-programming algorithm computes the edit distance of two length- n strings in O(n(2)) time, which is optimal up to subpolynomial factors assuming the Strong Exponential Time Hypothesis (SETH). An established way of circumventing this hardness is to consider the bounded setting, where the running time is parameterized by the edit distance k. A celebrated algorithm by Landau and Vishkin (JCSS'88) achieves a running time of O(n+ k(2)), which is optimal as a function of n and k (again, up to subpolynmial factors and assuming SETH). While the theory community thoroughly studied the Levenshtein distance, most practical applications rely on a more general weighted edit distance, where each edit has a weight depending on its type and the involved characters from the alphabet Sigma. This is formalized through a weight function w : Sigma boolean OR{epsilon}x Sigma U{epsilon} -> R normalized so that w(a bar right arrow a) = 0 for a is an element of Sigma boolean OR {epsilon} and w(a bar right arrow b) >= 1 for a, b is an element of Sigma boolean OR {epsilon} with a not equal= b;the goal is to find an alignment of the two strings minimizing the total weight of edits. The classic O(n(2))-time algorithm supports this setting seamlessly, but for many decades just a straightforward O(nk)-time solution was known for the bounded version of the weighted edit distance problem. Only very recently, Das, Gilbert, Hajiaghayi, Kociumaka, and Saha (STOC'23) gave the first non-trivial algorithm, achieving a time complexity of O(n + k(5)). While this running time is linear for k <= n(1/5), it is still very far from O(n + k(2))-the bound achievable in the unweighted setting. This is unsatisfactory, especially given the lack of any compelling evidence that the weighted version is in

关键词： edit distance conditional lower bounds string algorithms

来源：评论

学校读者我要写书评

暂无评论

Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts 30

Few Matches or Almost Periodicity: Faster Pattern Matching w...

引用

30th Annual ACM-SIAM Symposium on Discrete algorithms (SODA)

作者： Bringmann, Karl Kuennemann, Marvin Wellnitz, Philip Max Planck Inst Informat Saarland Informat Campus SIC Saarbrucken Germany Saarbrucken Grad Sch Comp Sci Saarbrucken Germany

ISBN: (纸本)9781611975482

A fundamental problem on strings in the realm of approximate string matching is pattern matching with mismatches: Given a text t, a pattern p, and a number k, determine whether some substring of t has Hamming distance at most k to p;such a substring is called a k-match. As real-world texts often come in compressed form, we study the case of searching for a small pattern p in a text t that is compressed by a straight-line program. This grammar compression is popular in the string community, since it is mathematically elegant and unifies many practically relevant compression schemes such as the Lempel-Ziv family, dictionary methods, and others. We denote by m the length of p and by n the compressed size of t. While exact pattern matching, that is, the case k = 0, is known to be solvable in near-linear time (O) over tilde (n + m) [Jez TALG'15], despite considerable interest in the string community, the fastest known algorithm for pattern matching with mismatches runs in time (O) over tilde (n root m poly(k)) [Gawrychowski, Straszak ISAAC'13], which is far from linear even for very small k. In this paper, we obtain an algorithm for pattern matching with mismatches running in time (O) over tilde ((n + m) poly(k)). This is near-linear in the input size for any constant (or slightly superconstant) k. We obtain analogous running time for counting and enumerating all k-matches. Our algorithm is based on a new structural insight for approximate pattern matching, essentially showing that either the number of k-matches is very small or both text and pattern must be almost periodic. While intuitive and simple for exact matches, such a characterization is surprising when allowing k mismatches.

关键词： stringology string algorithms approx. pattern matching grammar compression

来源：评论

学校读者我要写书评

暂无评论

Longest Common Substring Made Fully Dynamic 27

Longest Common Substring Made Fully Dynamic

引用

27th Annual European Symposium on algorithms (ESA)

作者： Amir, Amihood Charalampopoulos, Panagiotis Pissis, Solon P. Radoszewski, Jakub Bar Ilan Univ Dept Comp Sci Ramat Gan Israel Kings Coll London Dept Informat London England Interdisciplinary Ctr Herzliya Efi Arazi Sch Comp Sci Herzliyya Israel CWI Amsterdam Netherlands Univ Warsaw Inst Informat Warsaw Poland Samsung R&D Inst Warsaw Poland

ISBN: (纸本)9783959771245

Given two strings S and T, each of length at most n, the longest common substring (LCS) problem is to find a longest substring common to S and T. This is a classical problem in computer science with an O(n)-time solution. In the fully dynamic setting, edit operations are allowed in either of the two strings, and the problem is to find an LCS after each edit. We present the first solution to this problem requiring sublinear time in n per edit operation. In particular, we show how to find an LCS after each edit operation in (O) over tilde (n(2/3)) time, after (O) over tilde (n)-time and space preprocessing.(1) This line of research has been recently initiated in a somewhat restricted dynamic variant by Amir et al. [SPIRE 2017]. More specifically, they presented an (O) over tilde (n)-sized data structure that returns an LCS of the two strings after a single edit operation (that is reverted afterwards) in (O) over tilde (1) time. At CPM 2018, three papers (Abedin et al., Funakoshi et al., and Urabe et al.) studied analogously restricted dynamic variants of problems on strings. We show that the techniques we develop can be applied to obtain fully dynamic algorithms for all of these variants. The only previously known sublinear-time dynamic algorithms for problems on strings were for maintaining a dynamic collection of strings for comparison queries and for pattern matching, with the most recent advances made by Gawrychowski et al. [SODA 2018] and by Clifford et al. [STACS 2018]. As an intermediate problem we consider computing the solution for a string with a given set of k edits, which leads us, in particular, to answering internal queries on a string. The input to such a query is specified by a substring (or substrings) of a given string. Data structures for answering internal string queries that were proposed by Kociumaka et al. [SODA 2015] and by Gagie et al. [CCCG 2013] are used, along with new ones, based on ingredients such as the suffix tree, heavy-path decomposi

关键词： longest common substring string algorithms dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Internal Longest Palindrome Queries in Optimal Time 17th

Internal Longest Palindrome Queries in Optimal Time

引用

17th International Conference and Workshops on algorithms and Computation

作者： Mitanil, Kazuki Mieno, Takuya Seto, Kazuhisa Horiyama, Takashi Hokkaido Univ Grad Sch Informat Sci & Technol Sapporo Hokkaido Japan Univ Electrocommun Dept Comp & Network Engn Chofu Tokyo Japan Hokkaido Univ Fac Informat Sci & Technol Sapporo Hokkaido Japan

ISBN: (纸本)9783031270505;9783031270512

Palindromes are strings that read the same forward and backward. Problems of computing palindromic structures in strings have been studied for many years with a motivation of their application to biology. The longest palindrome problem is one of the most important and classical problems regarding palindromic structures, that is, to compute the longest palindrome appearing in a string T of length n. The problem can be solved in O(n) time by the famous algorithm of Manacher [Journal of the ACM, 1975]. In this paper, we consider the problem in the internal model. The internal longest palindrome query is, given a substring T[i..j] of T as a query, to compute the longest palindrome appearing in T[i..j]. The best known data structure for this problem is the one proposed by Amir et al. [Algorithmica, 2020], which can answer any query in O( log n) time. In this paper, we propose a linear-size data structure that can answer any internal longest palindrome query in constant time. Also, given the input string T, our data structure can be constructed in O(n) time.

关键词： string algorithms Palindromes Internal queries

来源：评论

学校读者我要写书评

暂无评论

Sublinear Time Lempel-Ziv (LZ77) Factorization 1

引用

30th International Symposium on string Processing and Information Retrieval (SPIRE) / 18th Workshop on Compression, Text, and algorithms (WCTA)

作者： Ellert, Jonas Tech Univ Dortmund Dortmund Germany

ISBN: (数字)9783031439803

ISBN: (纸本)9783031439797;9783031439803

The Lempel-Ziv (LZ77) factorization of a string is a widely-used algorithmic tool that plays a central role in data compression and indexing. For a length-n string over integer alphabet [0, sigma) with s = n(O(1)), and on a word RAM of width w = Theta(log n), it can be computed in O(n) time. However, the packed representation of the string occupies only Theta(n log sigma) bits or equivalently Theta(n / log(sigma) n) words of space, and hence we can hope for algorithms that run in O(n / log(sigma) n) time and words of space. Kempa showed how to compute the LZ77 factorization with overlaps in O(n / log(sigma) n+z log(11) n) time and O(n / log(sigma) n+z log(10) n) words of space, where z is the number of phrases in the LZ77 factorization (SODA 2019). We significantly improve this result by achieving O(n / log(sigma) n + z log(3+epsilon) z) time with overlaps, and O(n / log(sigma) n + z log(23/5+epsilon) z) without overlaps (for any constant epsilon is an element of R+). In both cases, we require only O(n / log(sigma) n) words of space. One ingredient of the solution is a novel approximation algorithm that computes an LZ-like parsing of at most 3z phrases in O(n / log(sigma) n) time and words of space. All algorithms are deterministic.

关键词： Lempel-Ziv LZ77 LZ-like lossless compression word-packing sublinear time string algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Utilizing dynamically updated estimates in solving the longest common subsequence problem

Utilizing dynamically updated estimates in solving the longe...

引用

12th International Conference on string Processing and Information Retrieval

作者： Bergroth, Lasse Turku Ctr Comp Sci Turku 20520 Finland

ISBN: (纸本)9783540297406

The running time of longest common subsequence (lcs) algorithms is shown to be dependent of several parameters, To such parameters belong e. g. the size of the input alphabet, the distribution of the characters in the input strings and the degree of similarity between the strings. Therefore it is very difficult to establish an lcs algorithm that could be efficient enough for all relevant problem instances. As a consequence of that fact, many of those algorithms are planned to be applied only on a restricted set of all possible inputs. Some of them are besides quite tricky to implement. In order to speed up the running time of lcs algorithms in common, one of the most crucial prerequisities is that preliminary information about the input strings could be utilized. In addition, this information should be available after a reasonably quick preprocessing phase. One informative a priori-value to calculate is a lower bound estimate for the length of the lcs. However, the obtained lower bound might not be as accurate as desired and thus no appreciable advantages of the preprocessing can be drawn. In this paper, a straightforward method for updating dynamically the lower bound value for the lcs is presented. The purpose is to refine the estimate gradually to prune more effectively the search space of the used exact lcs algorithm. Furthermore, simulation tests for the new presented method will be performed in order to convince us of the benefits of it.

关键词： longest common subsequence string algorithms heuristic algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast and Simple Circular Pattern Matching 3

Fast and Simple Circular Pattern Matching

引用

3rd International Conference on Man-Machine Interactions (ICMMI)

作者： Susik, Robert Grabowski, Szymon Deorowicz, Sebastian Lodz Univ Technol Inst Appl Comp Sci Al Politech 11 Lodz Poland Silesian Tech Univ Inst Informat PL-44100 Gliwice Poland

ISBN: (纸本)9783319023090

The problem of circular pattern matching is to find all rotations of a given pattern P in text T, both over a common alphabet. The pattern and any of its rotations are also called conjugates in the literature. For the online version of this problem we present a new general approach and use several matching techniques as components, based on bit-parallelism and filtering. The experimental results show the effectiveness of the method, with matching speeds reaching 7-8GB/s for long patterns and natural language or protein data.

关键词： combinatorial problems string algorithms circular pattern matching

来源：评论

学校读者我要写书评

暂无评论

Dotted suffix trees - A structure for approximate text indexing

引用

13th International Conference on string Processing and Information Retrieval

作者： Coelho, Luis Pedro Oliveira, Arlindo L. INESC-ID/IST Portugal

ISBN: (纸本)3540457747

In this work, the problem we address is text indexing for approximate matching. Given a text, T which undergoes some preprocessing to generate an index, we can later query this index to identify the places where a string occurs up to a certain number of errors k (edition distance). The indexing structure occupies space O(n log(k) n) in the average case, independent of alphabet size. This structure can be used to report the existence of a match with k errors in O(3(k) Mk+l) and to report the occurrences in O(3(k) m(k+l) + ed) time, where m is the length of the pattern and ed and the number of matching edit scripts. The construction of the structure has time bound by O(kN\Sigma\), where N is the number of nodes in the index and \Sigma\ the alphabet size.

关键词： string algorithms suffix trees approximate text matching text indexing

来源：评论

学校读者我要写书评

暂无评论

On Computing Average Common Substring Over Run Length Encoded Sequences

On Computing Average Common Substring Over Run Length Encode...

引用

2nd Student Conference on Mathematical Founcations in Bioinformatics

作者： Hooshmand, Sahar Tavakoli, Neda Abedin, Paniz Thankachan, Sharma V. Univ Cent Florida Dept Comp Sci 117 Harris Ctr Bldg 1164000 Cent Florida Blvd Orlando FL 32816 USA Georgia Inst Technol Sch Computat Sci & Engn Atlanta GA 30332 USA

The Average Common Substring (ACS) is a popular alignment-free distance measure for phylogeny reconstruction. The ACS of a sequence X[1, x] w.r.t. another sequence Y[1, y] is ACS(X, Y) = 1/x Sigma(x)(i=1) max lcp(X[i, x], Y[j, y]) The lcp(., .) of two input sequences is the length of their longest common prefix. The ACS can be computed in O(n) space and time, where n = x + y is the input size. The compressed string matching is the study of string matching problems with the following twist: the input data is in a compressed format and the underling task must be performed with little or no decompression. In this paper, we revisit the ACS problem under this paradigm where the input sequences are given in their run-length encoded format. We present an algorithm to compute ACS(X, Y) in O(N logN) time using O(N) space, where N is the total length of sequences after run-length encoding.

关键词： string algorithms Suffix Trees RL Encoding Compression

来源：评论

学校读者我要写书评

暂无评论

ACCELERATING THE UNDERSTANDING OF LIFE'S CODE THROUGH BETTER algorithms AND HARDWARE DESIGN

ACCELERATING THE UNDERSTANDING OF LIFE'S CODE THROUGH BETTER...

引用

作者： Mohammed H. K. Alser Bilkent University

学位级别：博士

Our understanding of human genomes today is affected by the ability of modern computing technology to quickly and accurately determine an individual's entire genome. Over the past decade, high throughput sequencing (HTS) technologies have opened the door to remarkable biomedical discoveries through its ability to generate hundreds of millions to billions of DNA segments per run along with a substantial reduction in time and cost. However, this flood of sequencing data continues to overwhelm the processing capacity of existing algorithms and hardware. To analyze a patient's genome, each of these segments - called reads - must be mapped to a reference genome based on the similarity between a read and "candidate" locations in that reference genome. The similarity measurement, called alignment, formulated as an approximate string matching problem, is the computational bottleneck because: (1) it is implemented using quadratic-time dynamic programming algorithms, and (2) the majority of candidate locations in the reference genome do not align with a given read due to high dissimilarity. Calculating the alignment of such incorrect candidate locations consumes an overwhelming majority of a modern read mapper's execution time. Therefore, it is crucial to develop a fast and effective filter that can detect incorrect candidate locations and eliminate them before invoking computationally costly alignment algorithms. In this thesis, we introduce four new algorithms that function as a pre-alignment step and aim to filter out most incorrect candidate locations. We call our algorithms GateKeeper, Slider, MAGNET, and SneakySnake. The first key idea of our proposed pre-alignment filters is to provide high filtering accuracy by correctly detecting all similar segments shared between two sequences. The second key idea is to exploit the massively parallel architecture of modern FPGAs for accelerating our four proposed filtering algorithms. We also develop an efficient CPU implementation

关键词： Read Mapping Approximate string Matching Read Alignment Levenshtein Distance string algorithms Edit Distance fast pre-alignment filter field-programmable gate arrays (FPGA)

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

全选清除本页清除全部题录导出标记到“检索档案”

共15页 << < 6 7 8 9 10 11 12 13 14 15 > >>

检索报告对象比较合并检索0

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

电话和邮箱必须正确填写，我们会与您联系确认。

联系人：

所在院系：

联系邮箱：

联系电话：

内蒙古自治区呼和浩特市赛罕区大学西街235号邮编: 010021

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：