What is meta? ×
Meta Stack Exchange is where users like you discuss bugs, features, and support issues that affect the software powering all 134 Stack Exchange communities.

This question: A data structure that maintain a set of strings, such that it returns strings matched by some regular expression was closed as not a real question (Note: It is not my question. Someone else has asked it).

It seems like a perfectly valid question to me. Is there some data structure which can support regex queries on some string repository. For an instance of an application of this, say you wanted to index the source code in your company. This type of a data structure might come in handy.

I admit I might be reading more than intended and it might be using subjective terms like 'efficient' and probably missing out some details (like single machine/distributed) etc, but it seems like a reasonable question. Objecively defining efficient each time would probably a waste of space/effort and time and the other info can easily be added. In any case, the question seems real enough to me, as it stands.

Can someone please explain why this is not a real question? Or get it reopened?

share|improve this question
3  
the other info can easily be added Then... add them. –  Yannis Mar 11 '13 at 3:29
1  
@Yannis: 1) The question seems real enough to me, as it stands. 2) I don't want to put words in the questioner's mouth. You do realize that the info I am talking about can only be given by the questioner? 3) I am new to this site and I am trying to understand the rules of this site... –  Knoothe Mar 11 '13 at 3:32
1  
Ah, sorry, I didn't notice it wasn't your question. Well, to answer one of your questions, a closed question can be re-opened if five people with 3K+ reputation vote to re-open it (that's the same reputation level required to vote to close). Every edit, even the smallest one, brings new attention to a question, and re-open votes are more likely to come when a question has been edited and improved. Thus, any clarifying edit would be the first step here. –  Yannis Mar 11 '13 at 3:34
    
@Yannis: Ah! No, I am not the questioner :-) –  Knoothe Mar 11 '13 at 3:35

2 Answers 2

up vote 4 down vote accepted

My guess is that the OP wants to index the strings in some way so that finding matches to a regex would be less expensive than a simple linear search. There are three major problems with this:

  • How efficient usage of a particular "data structure" would be is dependent on the language being used (or perhaps the OP means the strings are stored in a database?) This is not mentioned in the question

  • Whether the results are more efficient also depends on the size of S. Once again, this is not mentioned in the question. The OP could take an approach like n-gram indexing, which might end up being more expensive for small S, but increases efficiency as S becomes larger

  • Optimisation is an iterative process. An optimal approach can only be arrived at after a suboptimal approach is thoroughly fleshed out. Currently, answering the question would involve both coming up with an implementation and fine tuning it

Overall, the question is asking for optimisation of a vague algorithm that is intended to solve a poorly specified problem. If these problems can be fixed, the question might be reopened.


As a side note, there are entire academic papers written on the subject, so the question does seem to fail the FAQ requirement:

If you can imagine an entire book that answers your question, you’re asking too much.

share|improve this answer
    
Thank you for your answer. –  Knoothe Mar 11 '13 at 6:38

So...it seems that in the question, there's a lot of hand waving and "not paying attention to the man behind the curtain" here. That sort of question isn't really within the scope of StackOverflow.

Let's compare it to the list of what's considered on-topic at SO via the FAQ.

  • What specific problem is this?
  • Is this something one may encounter during their course of programming?

It honestly feels more like a CS.SE question, but I'd say it needs a little more fleshing out to even make it over there.

share|improve this answer
    
Thanks (+1, but I can't upvote yet). I would say both your bullet points are answered in the affirmative. I can understand the downvotes: no motivation/prior research. What I cannot understand is the closure. For instance, I would guess many data-structure questions would be similar. Anyway, I guess I need to do some more reading of the FAQ. –  Knoothe Mar 11 '13 at 3:59
1  
@Knoothe .. Then accept the answer instead? –  Daedalus Mar 11 '13 at 4:14
4  
@Daedalus: Too early to accept? Perhaps wait a day? What is the hurry? –  Knoothe Mar 11 '13 at 5:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .