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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入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

分类表

所选分类

>> <<

限定检索结果

文献类型

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

馆藏范围

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

日期分布

学科分类号

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

主题

150 篇 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...

语言

133 篇 英文
17 篇 其他

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

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

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

详细简洁

排序：

Estimating the Longest Increasing Subsequence in Nearly Optimal Time 63

Estimating the Longest Increasing Subsequence in Nearly Opti...

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Andoni, Alexandr Nosatzki, Negev Shekel Sinha, Sandip Stein, Clifford Columbia Univ New York NY 10027 USA

ISBN: (纸本)9781665455190

Longest Increasing Subsequence (LIS) is a fundamental statistic of a sequence, and has been studied for decades. While the LIS of a sequence of length n can be computed exactly in time O(n log n), the complexity of estimating the (length of the) LIS in sublinear time, especially when LIS << n, is still open. We show that for any n is an element of N and lambda = o(1), there exists a (randomized) non-adaptive algorithm that, given a sequence of length n with LIS >= lambda n, approximates the LIS up to a factor of 1/lambda(o(1)) in n(o(1))/lambda time. Our algorithm improves upon prior work substantially in terms of both approximation and run-time: (i) we provide the first sub-polynomial approximation for LIS in sub-linear time;and (ii) our run-time complexity essentially matches the trivial sample complexity lower bound of Omega(1/lambda), which is required to obtain any non-trivial approximation of the LIS. As part of our solution, we develop two novel ideas which may be of independent interest. First, we define a new Genuine-LIS problem, in which each sequence element may be either genuine or corrupted. In this model, the user receives unrestricted access to the actual sequence, but does not know a priori which elements are genuine. The goal is to estimate the LIS using genuine elements only, with the minimal number of tests for genuineness. The second idea, Precision Tree, enables accurate estimations for composition of general functions from "coarse" (sub-)estimates. Precision Tree essentially generalizes classical precision sampling, which works only for summations. As a central tool, the Precision Tree is pre-processed on a set of samples, which thereafter is repeatedly used by multiple components of the algorithm, improving their amortized complexity.

关键词： sublinear algorithms approximation algorithms randomized algorithms longest increasing subsequence string 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

来源：评论

学校读者我要写书评

暂无评论

Longest Common Prefix Arrays for Succinct k-Spectra 1

引用

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

作者： Alanko, Jarno N. Biagi, Elena Puglisi, Simon J. Univ Helsinki Dept Comp Sci HIIT Helsinki Finland

ISBN: (数字)9783031439803

ISBN: (纸本)9783031439797;9783031439803

The k-spectrum of a string is the set of all distinct substrings of length k occurring in the string. K-spectra have many applications in bioinformatics including pseudoalignment and genome assembly. The Spectral Burrows-Wheeler Transform (SBWT) has been recently introduced as an algorithmic tool to efficiently represent and query these objects. The longest common prefix (LCP) array for a k-spectrum is an array of length n that stores the length of the longest common prefix of adjacent k-mers as they occur in lexicographical order. The LCP array has at least two important applications, namely to accelerate pseudo-alignment algorithms using the SBWT and to allow simulation of variable-order de Bruijn graphs within the SBWT framework. In this paper we explore algorithms to compute the LCP array efficiently from the SBWT representation of the k-spectrum. Starting with a straightforward O(nk) time algorithm, we describe algorithms that are efficient in both theory and practice. We show that the LCP array can be computed in optimal O(n) time, where n is the length of the SBWT of the spectrum. In practical genomics scenarios, we show that this theoretically optimal algorithm is indeed practical, but is often outperformed on smaller values of k by an asymptotically suboptimal algorithm that interacts better with the CPU cache. Our algorithms share some features with both classical Burrows-Wheeler inversion algorithms and LCP array construction algorithms for suffix arrays. Our C++ implementations of these algorithms are available at https://***/jnalanko/kmer-lcs.

关键词： longest common prefix LCP longest common suffix k-mer string algorithms compressed data structures de Bruijn graph Burrows-Wheeler transform BWT

来源：评论

学校读者我要写书评

暂无评论

Parallel Longest Common SubSequence Analysis In Chapel

Parallel Longest Common SubSequence Analysis In Chapel

引用

IEEE High Performance Extreme Computing Virtual Conference (HPEC)

作者： Vahidi, Soroush Schieber, Baruch Du, Zhihui Bader, David A. New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA New Jersey Inst Technol Dept Data Sci Newark NJ USA

ISBN: (纸本)9798350308600

One of the most critical problems in the field of string algorithms is the longest common subsequence problem (LCS). The problem is NP-hard for an arbitrary number of strings but can be solved in polynomial time for a fixed number of strings. In this paper, we select a typical parallel LCS algorithm and integrate it into our large-scale string analysis algorithm library to support different types of large string analysis. Specifically, we take advantage of the high-level parallel language, Chapel, to integrate Lu and Liu's parallel LCS algorithm into Arkouda, an open-source framework. Through Arkouda, data scientists can easily handle large string analytics on the back-end high-performance computing resources from the front-end Python interface. The Chapel-enabled parallel LCS algorithm can identify the longest common subsequences of two strings, and experimental results are given to show how the number of parallel resources and the length of input strings can affect the algorithm's performance.

关键词： string algorithms parallel computing Chapel programming language

来源：评论

学校读者我要写书评

暂无评论

A Formal Framework for stringology 19

A Formal Framework for Stringology

引用

Prague stringology Conference (PSC)

作者： Mhaskar, Neerja Soltys, Michael McMaster Univ Dept Comp & Software 1280 Main St West Hamilton ON L8S 4K1 Canada Calif State Univ Channel Isl Dept Comp Sci Camarillo CA 93012 USA

ISBN: (纸本)9788001057872

A new formal framework for stringology is proposed, which consists of a three-sorted logical theory S designed to capture the combinatorial reasoning about finite words. A witnessing theorem is proven which demonstrates how to extract algorithms for constructing strings from their proofs of existence. Various other applications of the theory are shown. The long term goal of this line of research is to introduce the tools of Proof Complexity to the analysis of strings.

关键词： proof complexity string algorithms

来源：评论

学校读者我要写书评

暂无评论

Utilizing dynamically updated estimates in solving the longest common subsequence problem

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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)

来源：评论

学校读者我要写书评

暂无评论

Self-normalised distance with don't cares

Self-normalised distance with don't cares

引用

18th Annual Symposium on Combinatorial Pattern Matching

作者： Clifford, Peter Clifford, Raphael Univ Oxford Dept Stat Oxford England Univ Bristol Dept Comp Sci Bristol Avon England

ISBN: (纸本)9783540734369

We present O(n log m) algorithms for a new class of problems termed self-normalised distance with don't cares. The input is a pattern p of length m and text t of length n > m. The elements of these strings are either integers or wild card symbols. In the shift version, the problem is to compute min(alpha) Sigma(m-1)(j-0)(alpha + P-j - t(i+j))(2) for all i, where wild cards do not contribute to the sum. In the shift-scale version, the objective is to compute min(alpha,beta) Sigma(m-1)(j=0)(alpha + beta p(j) - t(i+j))(2) for all i, similarly. We show that the algorithms have the additional benefit of providing simple O(n log m) solutions for the problems of exact matching with don't cares, exact shift matching with don't cares and exact shift-scale matching with don't cares.

关键词： algorithms and data structures pattern matching string algorithms

来源：评论

学校读者我要写书评

暂无评论

Subsequence Covers of Words 29th

Subsequence Covers of Words

引用

29th International Symposium on string Processing and Information Retrieval (SPIRE)

作者： Charalampopoulos, Panagiotis Pissis, Solon P. Radoszewski, Jakub Rytter, Wojciech Walen, Tomasz Zuba, Wiktor Birkbeck Univ London London England CWI Amsterdam Netherlands Vrije Univ Amsterdam Netherlands Univ Warsaw Warsaw Poland

ISBN: (纸本)9783031206429;9783031206436

We introduce subsequence covers (s-covers, in short), a new type of covers of a word. A word C is an s-cover of a word S if the occurrences of C in S as subsequences cover all the positions in S. The s-covers seem to be computationally much harder than standard covers of words (cf. Apostolico et al., Inf. Process. Lett. 1991), but, on the other hand, much easier than the related shuffle powers (Warmuth and Haussler, J. Comput. Syst. Sci. 1984). We give a linear-time algorithm for testing if a candidate word C is an s-cover of a word S over a polynomially-bounded integer alphabet. We also give an algorithm for finding a shortest s-cover of a word S, which in the case of a constant-sized alphabet, also runs in linear time. Furthermore, we complement our algorithmic results with a lower and an upper bound on the length of a longest word without non-trivial s-covers, which are both exponential in the size of the alphabet.

关键词： string algorithms Combinatorics on words Covers Shuffle powers Subsequence covers

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

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

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：