as i am new in lisp
so i need help to implement dis follwing algorithm in lisp
Algorithm PathModelConstruction (n: length of n-gram;
L: log file of sessions; T: table indexed by all n-grams of
all sessions in L)
Begin
L := Filter(L); // we will explain how to filter log file L
later;
T[] := 0; // Initialize Table T to zero for all n-grams
H[] := 0; // result of the model is stored in hash table H(),
indexed on n-grams
Max[] := 0 // Max[] records the maximum count for each
n-gram
For i:= 1 to |L| Do
S := L[I];
For j:=1 to |S| do
If (|S| - j)>n Then
// find a sub-string of length n starting at alphabet j
P := sub-string S, j, n;
C := sub-string(S,j+1,1); // find the next click
T[P,C] := T[P,C] + 1;
If T[P,C] > Max[P] Then
H[P] := C;
End If
End If
End For
End For
Return H[];
example
As an example, consider a log file L consisting of the
following request paths:
A,B,C,D
A,B,C,F
A,B,C,F
B,C,D,G
B,C,D,G
B,C,D,F
If we were to construct a 3-gram model, we have two 3-
grams to build our prediction model on. These are
A,B,C; B,C,D
Our application of the algorithm returns the following hash
table H3():
N-Gram Prediction
A,B,C F
B,C,D G
From: Pascal J. Bourguignon
Subject: Re: need help to implement a prefetch algoritm in lisp
Date:
Message-ID: <87vdtd3h9i.fsf@informatimago.com>
··············@gmail.com" <·············@gmail.com> writes:
> as i am new in lisp
> so i need help to implement dis follwing algorithm in lisp
There are different degrees in translating an algorithm. You can do a
word-for-word translation, or you may understand the algorithm and
rewrite it with the higher level notions provided by the language.
Let's start with a word-for-word translation. This procedural algorithm
defines a function, is build of sequential statements, function calls,
local variables, assign values to variables, uses arrays, hash-tables,
strings, alternatives, loops, etc.
So you will have to learn how to write these basic constructs in Lisp to
be able to compose a word-for-word lisp program implementing this
algorithm.
Start reading some of the tutorials indicated at:
http://www.cliki.net/Online%20Tutorial
Or you could try to browse the CLHS at:
http://www.lispworks.com/documentation/HyperSpec/Front/index.htm
for example, chapter 5 gives the basic statements such as the sequence
PROGN, the alternative IF, the local variable definition LET, etc.
> Algorithm PathModelConstruction (n: length of n-gram;
> L: log file of sessions; T: table indexed by all n-grams of
> all sessions in L)
> Begin
> L := Filter(L); // we will explain how to filter log file L
> later;
> T[] := 0; // Initialize Table T to zero for all n-grams
> H[] := 0; // result of the model is stored in hash table H(),
> indexed on n-grams
> Max[] := 0 // Max[] records the maximum count for each
> n-gram
> For i:= 1 to |L| Do
> S := L[I];
> For j:=1 to |S| do
> If (|S| - j)>n Then
> // find a sub-string of length n starting at alphabet j
> P := sub-string(S, j, n);
> C := sub-string(S,j+1,1); // find the next click
> T[P,C] := T[P,C] + 1;
> If T[P,C] > Max[P] Then
> H[P] := C;
> End If
> End If
> End For
> End For
> Return H[];
For example, let's take the statement L := Filter(L);
Since it is pseudocode, the meaning of this statement is less than
clear.
L is said to be a log file of sessions. A file.
What would assigning to a file mean? Does it mean the file in the file
system must be replaced by another file? Or does it mean that L is a variable
referencing to a file in the file system, and it should now refer to
another file? Or does the variable L hold the contents of the file?
Will the function Filter new contents?
These questions have nothing to do with the programming language, it's
for you to determine what that should mean. But assuming the needed
abstraction, therefore taking the statement literally, such an
assignment to a formal parameter of the result of a function call could
be written in Lisp as:
(setf l (filter l))
The assumed abstraction will be embodied in functions used to translate
pseudo-code syntax such as: L[I] or |L|. You could write
(logfile-ref l i) ; for L[I] and
(logfile-size l) ; for |L|.
and implement these functions later depending on the actual data type
of L.
--
__Pascal Bourguignon__