Re: String searching and lienar optimization


In article <7996825f-4617-4ec4-bef8-5df0b045c794@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"almurph@xxxxxxxxxxxxx" <almurph@xxxxxxxxxxxxx> writes:
On Jun 4, 5:16=A0pm, Gordon Sande <g.sa...@xxxxxxxxxxxxxxxx> wrote:
On 2008-06-04 12:43:46 -0300, "almu...@xxxxxxxxxxxxx"
<almu...@xxxxxxxxxxxxx> said:

Thank gordon, but this is not really what i am after.

Al.

Perhaps you can give better hints of what you are after
as you have provided a good description of pattern matching.
There are *lots* of things known about pattern matching.
It is both very useful and simple enough to model that that
it is subject to many different kind of analyses.





Gordon Sande wrote:

On 2008-06-04 08:50:50 -0300, "almu...@xxxxxxxxxxxxx"
<almu...@xxxxxxxxxxxxx> said:

Hi,

Hope you can help me here and apologies if i'm in the wrong forum.
I want to use a linear programming technique to optimize the searching=

of a string (and string like it) inside another (much longer) string.
For example say I am looking for the pattern "abdf" inside the
string: "fjwkrjweoriosdaicfosdifidoiasosifosdifosdfio" for example..
Can this problem be posed suitable lfor linear optimization?

I would appreciate any comments/suggestions/ideas that you may be
able to offer and apologies again if I'm in the wrong form.

Thanking you,
Al.

Try computer algorithms as a field and pattern matching as a topic.
There are standard packages for this that often have GREP (after
the Unix command) in their names.- Hide quoted text -

- Show quoted text -

I agree. What I am trying to do is to structure a string searching
process (like the one mentioned above) in a form suitable for linear
programming. I know this is unusual, I'm not even sure it is possible
BTW. I suspect that I will have to build some sort of intermediate
object like some sort of tree (perhaps suffix tree) or graph perhaps
and use this to structure the problem suitable for linear
optimization. I have the added problem that the search strig gets
longer so the intermediate object (what ever that will be) needs to be
scalable easily.
Hope this explains what I'm after. I have googled for string searching
techniques (both exact and 'fuzzy') and linear programming but not
much there. This is why I nned to restructure the problem suitable for
linear optimization (if possible).
Hope this helps,
Al.

a string and distances in strings will be necessarily discrete objects.
hence if there is a relation to LP than at most ILP. but ILP is
of exponential complexity and it is quite unclear how it should help here.
btw: in your example the search string didn't occur at all:
do you want to allow interruptions by other symbols and want to search for
the occurence with the "shortest" interruptions ?
hth
peter

.

Relevant Pages

  • Re: Paper & pencil password algorithm
    ... it is important for the hash function to be non-linear. ... Composition of linear is linear. ... even with a cycle length of millions, it guarantees no security. ... Doing 4 rounds on a 10 digit string ...
    (sci.crypt)
  • RE: Oject value changing in a loop
    ... Sub zString_FindGeneral(ByRef IFindThis As String, ... ByRef IFmRow As Long, ByRef IFmCol As Integer, ByRef IToRow As Long, ByRef ... ' OFoundQty is the number of cells found containing the IFindThis string. ... 'Lines A, D, E work when searching one or multiple worksheets ...
    (microsoft.public.excel.programming)
  • Re: Parameter Query Form Problem
    ... Dim stDocName As String ... This is what I used to make my query, its was a Microsoft support site. ... controls on the form so it can run the query. ... Combo Box for searching Customer Name ...
    (microsoft.public.access.formscoding)
  • Re: string comparision in a file
    ... rakesh wrote: ... String which needs to be searched would be ... I would also welcome any other better of handling searching ... and there is considerable overhead time when reading a line (such as ...
    (comp.lang.cpp)
  • Re: Fastest way to search text file for string
    ... I'm searching a text file for a given string -- ... "I don't want to load the entire file into physical memory" ... Not stuck, that is the requirement. ...
    (microsoft.public.dotnet.languages.csharp)