Questions about sequences of symbols, sets thereof and their properties as well as uses.

learn more… | top users | synonyms

0
votes
0answers
20 views

How to find close match of levenshtein distance [duplicate]

Let's say we have some function, float distance(String a, String b) { /*...*/ } to find the Levenshtein distance between two strings, and we have a large array ...
6
votes
2answers
453 views

Compression type that can be searched

Is there ANY compression type that can compress a file, and then that compressed file can be searched without uncompressing the file?
6
votes
0answers
51 views

Edit distance of list with unique elements

Edit distance (Levenshtein-Distance) between lists is a well studied CS-problem, but I can't find much on possible improvements if it is known that an element does not occur more than once in each ...
6
votes
1answer
36 views

Does the Rabin-Karp really need me to care about applying a mod Q operation on the rolling hashes?

I have been reading about the Rabin Karp algorithm and I kept wondering what's the big deal with keeping our rolling hashes values bounded by a value Q? I'd thought that as our integer number ...
0
votes
0answers
19 views

Are there any algorithms or researches on finding local alignments in partially ordered sequences?

The question is a bit unclear, so let me explain. Finding local alignments in sequences like protein sequence is a well studied area in bioinformatics, and I do not think there is any lack of ...
2
votes
2answers
79 views

Universal binary rewriting system

What is the simplest example of a rewriting system from binary strings to binary strings $$f:\Sigma^*\rightarrow\Sigma^*\qquad\Sigma=\{0,1\}$$ that can perform universal computation? Binary string ...
2
votes
0answers
53 views

KMP Algorithm, Pratt's Minimisation/optimization of Knuth's original DFA based algorithm

The Original Knuth's Algorithm is based on DFA and it depends on the alphabet size. And Then, Pratt optimised it to be independent of Alphabet Size. But, All the ...
0
votes
2answers
68 views

Minimal length of a string that contains two strings

We have two strings $a,b$. I want to find string $c$ that includes $a$ as a subsequence and includes $b$ as a subsequence and the length of $c$ is minimal. Is there an efficient algorithm for this ...
2
votes
0answers
32 views

Can smart recursive search find all optimal solutions for Closest String?

Consider the Closest String problem: Input: Strings $s_1, \dots, s_m \in \Sigma^n$ and $k \in \mathbb{N}$. Question: Is there $s \in \Sigma^n$ for which $d_H(s, s_i) \leq k$ for all $i ...
1
vote
0answers
24 views

Find maximum scoring characters with non overlapping occurrences from a string

I have a problem related to Episode Mining in which I need to find the maximal utility of a episode given its occurrences in an event sequence.But I am presenting the question in a different form so ...
1
vote
0answers
27 views

What is the intuition behind the “edit sensitive parsing” tree?

If I understand right then ESP tree is defined as : given any string $x$ of finite length over an alphabet one can construct "an" ESP tree corresponding to it say $T_x$ such that each leaf of the tree ...
5
votes
1answer
45 views

Hamiltonian circuit for a family of graphs

For $\Sigma = \{a,b\}$, let $S_n = \{w\mid w \in \Sigma^{*} \land |w| = n\}$. Let $C_n \subset \Sigma^{*}$ be the language of circular strings that contain as substrings all elements of $S_n$. For ...
3
votes
1answer
142 views

Algorithm to search substring in a circular string?

I need an algorithm to search for substrings. I checked different resources, and it seems that the most known algorithms are the Boyer–Moore and the Knuth–Morris–Pratt. However, as far as I ...
2
votes
1answer
50 views

Searching for multiple partial phrases so that one original phrase can not match multiple search phrases

Given a predefined set of phrases, I'd like to perform a search based on user's query. For example, consider the following set of phrases: ...
2
votes
2answers
444 views

What are the k characters which make the most complete words?

Given a word list of $N$ words formed from a language of $M$ characters, where each word is composed of $n \geq 1$ not necessarily distinct characters, how can I find the best set of $k<M$ ...
1
vote
1answer
41 views

Sequence alignment with one to many characters

I'm trying to align a sequence of characters together, I found that sequence alignment algorithms which use dynamic programming like Needleman-Wunsch or Smith–Waterman only align one character with ...
0
votes
0answers
14 views

Effect of mismatches on string matching finite automata

I am contemplating a string matching FA algorithm (not KMP). The complexity of its transition function calculation ie the preprocessing is m(length of pattern )* (the language of the FA) . What effect ...
2
votes
0answers
59 views

How does a minimal DFA ensure minimal computational cost?

I just went to read wikipedia to check a point on FA minimization, and I read there the following sentence: The minimal DFA ensures minimal computational cost for tasks such as pattern matching. ...
1
vote
0answers
92 views

How can I learn Sunday's string searching algorithm?

How does Sunday's string searching algorithm work? I am highly unskilled in processing mathematical lingo, so I would appreciate a use case/example. A link would be ok. I tried searching the first 6 ...
2
votes
3answers
40 views

Existence of functions that only tests memberships without revealing any information about the members

Given a set of strings $\{s_1, s_2, \cdots, s_n\}$, is there a way to encode them to a program $P$, such that given some string,$s$, the program can test the membership efficiently (deterministically ...
2
votes
1answer
78 views

Generating symbol matrices that satisfy regular expressions row- and column-wise

I have a program that fills a matrix of size N with characters such that all words formed by each row satisfy one regular expression, and all the words formed by each column satisfies a second one. ...
-1
votes
2answers
70 views

Finding A String Using A Suffix Array/Table

Is it possible to find out a string only having its corresponding suffix array/table and knowing that the string contains only, for instance, letters "f", "g", "r"? If so, how is that possible?
-1
votes
1answer
26 views

String distance metric for possibly truncated words

I am looking for the optimal string distance metric to indicate similarity/difference between possibly truncated words. For example, I would like to find the distance metric between the name "Richard" ...
1
vote
0answers
27 views

Constructing a TM from empty string

Hey I want to construct a deterministic Turing Machine, which out of an empty string tapes six consecutive 1s when halt. I have a question, is it possible to create such without transitions from final ...
5
votes
1answer
59 views

Understanding the heuristic used for approximate string searching through an FSA

The paper I'm looking at: Fast approximate string matching with finite automata (2009) Explanation of the algorithm (from my understanding anyway): A word is inputted into the automaton and from ...
1
vote
3answers
123 views

Fastest possible way to check what of X is in a string

I am trying to speed up one of my application, one of the places where I can speed up is in my test if a string contains an array of strings. example: I have the matches "dog", "cat" "apple" and the ...
0
votes
1answer
87 views

Efficiently count frequency of n-grams at start of words

I have a text file with all possible 5-grams (26^5 = 11.881.376) organized in rows as: aaaaa aaaab aaaac aaaad ..... and I have a txt file (organized in rows) with all English words. I have to find ...
2
votes
1answer
97 views

How to create a suffix tree by hand

I will soon have to be able to draw a suffix tree of a word on an exam. I tried to understand the different algorithms available, but they seem rather complicated to do "by hand". I do not see a ...
5
votes
1answer
109 views

How do I efficiently checking if a string matches any substring in a collection

I have a collection of substrings "this" "is" "a" "antelope" I need to look at any given string and answer the question "Are any of the given substrings in this ...
4
votes
0answers
67 views

Number of distinct substrings

I know how to find the number of distinct substrings for a string (using suffix arrays) and I was wondering if there was a way to find this number for all of its prefixes. I already have an $O(N^2)$ ...
1
vote
0answers
83 views

What is MongeElkan distance between words? [duplicate]

i used CosineSimilarity, EuclideanSimilarity, LevenshteinSimilarity and known about how it ...
0
votes
1answer
98 views

FM-index - print all patterns

How is it possible to print all patterns, of length k, contained in a string using FM-index and burrows-wheeler transform? PROBLEM DETAIL: I think it's better to leave more details regarding my ...
1
vote
0answers
34 views

Modify Damerau–Levenshtein distance to allow reversals of longer substrings

Is there a way to modify the Damerau–Levenshtein distance algorithm to allow the transposition of substrings? By this I mean that instead of simply turning "ba" to "ab" you could calculate "worra" to ...
1
vote
0answers
52 views

Using A* to find the word closest to an input rejected by a finite automaton

In the article Fast approximate string matching with finite automata by M. Hulden (2009) (mostly pages 58/59), the author describes how to search for a closest matching string word from an automaton ...
4
votes
0answers
49 views

Polynomial time algorithms on strings [closed]

I am looking for familiar problems on strings of finite length over an finite alphabet, where a polynomial time algorithm is known. To be more precise, let $\Sigma$ be a finite alphabet. I am looking ...
2
votes
3answers
126 views

Computing the closest match of an automaton and a string

I have a problem where I'm trying to find an efficient algorithm for approximate string matching for an input to the closest string match from an automaton (the input is assumed to be not accepting ...
8
votes
1answer
260 views

Given n strings, is one of them a substring of another?

Suppose we are given a collection of $n$ strings, $S_1,\dots,S_n$. I would like to know whether any of those strings is a substring of any other string in the collection. In other words, I'd like an ...
1
vote
1answer
37 views

FM-index and pattern search with wildcards

in one of my algorithm courses i'm studying the FM-Index. In one of the exercise I'm trying to do I was asked to give a procedure to search patterns of the form w* ...
2
votes
2answers
114 views

A reference for pseudocode for Monge-Elkan algorithm?

Does anyone have a good reference to pseudocode for Monge-Elkan string comparison algorithm? I have access to the two original papers, but they do not show the pseudocode of the actual algorithm. ...
2
votes
1answer
404 views

compressing a set of binary strings with fixed length

I'm looking for a data structure / algorithm to store an unordered set S of binary strings of a fixed length n (i.e. all ...
0
votes
1answer
235 views

Which algorithm to use to find all common substring (LCS case) with really big strings

I'm looking for a particular case of longest common substring (LCS) problem. In my case I have two really big strings (tens or hundreds of milions byte characters) and need to find the LCS and other ...
2
votes
2answers
233 views

Segmenting an English string with no spaces using dynamic programming

Suppose you have a function quality(x) that returns the quality of a sequence of letters x. Given a string such as ...
5
votes
1answer
257 views

Proving optimality of a dynamic programming algorithm

We have a string $s$ containing $n \leq 100$ bits. The move we can make on it is erasing from $s$ some substring $x$, but only if $x$ is directly preceded by $x^R$, where $x^R$ means string $x$ ...
1
vote
2answers
99 views

Enumerate All Possible Strings Over Alphabet

I am given the following decision problem: A program $ \Pi $ takes as input a pair of strings and outputs either $true$ or $false$. It is guaranteed that $\Pi$ terminates on any input. Does there ...
1
vote
1answer
46 views

Algorithm to merge two incomplete lists of symbols (strings) into a complete one

I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution. Let's say we have two ordered lists of symbols (strings): ...
1
vote
0answers
92 views

Boyer-Moore with Don't Cares

I have been doing a lot of research into pattern matching algorithms. For some background I am searching a long binary alphabet text consisting of considerably more 0s than 1s. The individual ...
1
vote
2answers
59 views

Is string matching and replacement considered in formal languages?

Is string matching and replacement, as an operation on strings or on formal languages, considered in formal languages? For example, the family of regular languages, or the family of context free ...
4
votes
0answers
188 views

Complexity of a naive algorithm for finding the longest Fibonacci substring

Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows: $$ F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1 \\ F(k-1) ...
1
vote
2answers
988 views

Edit distance (Levenshtein-Distance) algorithm explanation

I want to calculate the edit distance (aka Levenshtein-Distance) between two words: «solo» and «oslo». According to this site we'll get the result matrix: What I don't understand is: In case of ...
0
votes
1answer
55 views

What string operations are basic

What string operations are basic in the sense that the other string operations can be represented in terms of them? Here is a list of string operations off the top of my head (not necessarily a ...