An extractive RAG answer with a citation

A model-free RAG system: find the single sentence in the documents that best matches the question, and answer with it and its source.

What to build

A program that answers a question by extracting the best-matching sentence from a set of documents.

Requirements

  • Question words: the different words of the question, lower-cased and stripped of .,?!, minus the stop words.
  • Split each document into sentences at . (ignoring empty pieces and surrounding spaces); a sentence's score is the number of different question words among its words (matched the same way).
  • Print answer: SENTENCE. [source D] for the highest-scoring sentence (the earliest document, then the earliest sentence, on a tie), keeping its original capitals.
  • If every sentence scores 0, print answer: I do not know.

Input

Line 1: the stop words. Line 2: n. Then n documents. Then the question.

Output

One line.

Constraints

1 ≤ n ≤ 100; each document has at most 100 sentences.

Example

Input:

the a is at when does what
2
The library opens at nine. It closes at six.
The cafe opens at eight. Coffee is free on Mondays.
is coffee free

Output:

answer: Coffee is free on Mondays. [source 2]

Why it works

Sentences that contain more of the question's meaningful words are more likely to answer it, and refusing when nothing matches is the extractive version of "say you do not know".

Examples

Example 1 · Input
the a is at when does what
2
The library opens at nine. It closes at six.
The cafe opens at eight. Coffee is free on Mondays.
is coffee free
Expected output
answer: Coffee is free on Mondays. [source 2]
Example 2 · Input
the
1
Rain falls. Snow melts.
when does the sun rise
Expected output
answer: I do not know

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Lower-case everything for matching, strip `.,?!` from words, and drop the stop words from the question.

Hint 2

Split each document into sentences at `.`; score each sentence by the number of different remaining question words it contains.

Hint 3

Answer with the best sentence (earliest on a tie) as written, plus a full stop and its source number.

Solution

Show one correct solution (try it yourself first)
stop = set(input().lower().split())
n = int(input())
docs = [input() for _ in range(n)]
question = input()


def words(text):
    return {w.strip(".,?!").lower() for w in text.split()}


q = words(question) - stop
best = None
for d, doc in enumerate(docs, 1):
    for sentence in [s.strip() for s in doc.split(".") if s.strip()]:
        score = len(q & words(sentence))
        if score > 0 and (best is None or score > best[0]):
            best = (score, sentence, d)
if best is None:
    print("answer: I do not know")
else:
    print(f"answer: {best[1]}. [source {best[2]}]")

Lesson: Retrieval-augmented generation (RAG) →